链表有无环以及确定入环口详解

142.环形链表 II

        给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

        如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0

输出:返回索引为 0 的链表节点 解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1

输出:返回 null 解释:链表中没有环。


判断是否有环


算法思想:经典的快慢指针问题,设置快慢指针,slow 和 fast 初始时都指向链表的头结点 head,然后慢指针每次走一步,快指针每次走两步,这样快指针一定比慢指针先入环,经过不断的走下去,若是链表有环,快慢指针必会在环上相遇

#include<iostream>
#include<math.h>
using namespace std;
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};bool hasCycle(ListNode* head) {if (head == nullptr || head->next == nullptr) return false;	// 链表没有元素或者只有一个元素ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) return true;}return false;}

判断入环口


        判断链表的入环口相当于判断两长度不一的链表的公共结点初始位置(长的先走两链表的差值,然后一起走),按道理我们应该让长的链表先走(假设长链表是初始链表,短链表是从环开始的链表),由于链表有环我们无法准确的知道链表的长度,那么如何判断入环口呢?

        首先我们应该知道,在 slow 入环的时候,fast 早已入环,那么 slow 和 fast 之间的距离必定小于环长,所以当 fast 和 slow 相遇的时候,slow 在环内走的距离一定小于环长。

        我们假设头结点距离入环口的长度为 a ,fast 和 slow 相遇的位置距离入环口 x ,环的长度为 r .那么由上图可知 slow 走的距离是 a+x,而由于相遇之前 fast 可能已经绕环 n 圈,那么 fast 所走的距离是 a + r*n + x,又由于 fast 所走的步长等于 slow 的两倍,所以 2*(a+x) = a + r*n + x => a = r*n - x。

再回到寻找两链表的公共结点,我们已经知道了链表长度的差值 a,又已知链表是有环的,那么不妨设 h1 = head, h2=slow( 相对于h1已经走了 x ),那么 h1 走完 a 到达入环口的时候,h2 已经绕完环 n 圈也到达了入环口,所以 h1 和 h2 相遇的位置便是入环口的位置。

/*142. 环形链表 II
*/#include<iostream>
using namespace std;/* 链表类型 */
typedef struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};ListNode* detectCycle(ListNode* head) {if (head == nullptr || head->next == nullptr) return nullptr;if (head->next == head) return head;                            // 只有头结点ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) break;}if (fast == nullptr || fast->next == nullptr) return nullptr;   // 无环ListNode* h1 = head;ListNode* h2 = slow;while (h1 != h2) {h1 = h1->next;h2 = h2->next;}return h1;                                                      // 入环口
}

over!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/85166.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis的事务和watch机制

这里写目录标题 第一章、redis事务和watch机制1.1&#xff09;redis事务&#xff0c;事务的三大命令语法&#xff1a;开启事务 multi语法&#xff1a;执行事务 exec语法&#xff1a;取消事务 discard 1.2&#xff09;redis事务的错误和回滚的情况1.3&#xff09;watch机制语法&…

Django框架-使用celery(一):django使用celery的通用配置,不受版本影响

目录 一、依赖包情况 二、项目目录结构 2.1、怎么将django的应用创建到apps包 三、celery的配置 2.1、celery_task/celery.py 2.2、celery_task/async_task.py 2.3、celery_task/scheduler_task.py 2.4、utils/check_task.py 四、apps/user中配置相关处理视图 4.1、基本…

Vue [Day7] 综合案例

核心概念回顾 state&#xff1a;提供数据 getters&#xff1a;提供与state相关的计算属性 mutations&#xff1a;提供方法&#xff0c;用于修改state actions&#xff1a;存放异步操作 modules&#xff1a;存模块 功能分析 https://www.npmjs.com/package/json-server#ge…

3.UE基本操作及数字人工程模块组成(UE数字人系统教程)

1.Fay-UE5数字人工程导入 2.UE数字人语音交互 3.UE基本操作及数字人工程模块组成&#xff08;UE数字人系统教程&#xff09; 一、ue5基本操作 1、项目文件管理 2、关卡素材编辑 在关卡上&#xff1a;w、s、a、d移动&#xff0c;鼠标右键拖动换视角。 二、数字人工程模…

开源力量再现,国产操作系统商业化的全新探索

文章目录 1. 开源运动的兴起2. 开源力量的推动3. 国产操作系统的崭露头角3.1 国产操作系统有哪些 4.国产操作系统的商业化探索5.开源力量对国产操作系统商业化的推动 操作系统作为连接硬件、中间件、数据库、应用软件的纽带&#xff0c;被认为是软件技术体系中最核心的基础软件…

火爆全网,HttpRunner自动化测试框架-parameters参数化(超细整理)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在使用HttpRunner…

Tomcat的一些配置问题(server.xml/catalina.sh)

在同一机器中运行多个Tomcat时&#xff0c;如果不修改server.xml的端口参数&#xff0c;会出现端口冲突使得Tomcat异常&#xff1b;Tomcat默认配置中&#xff0c;JAVA_OPTS不会设置太大&#xff0c;一般需要在catalina.sh中增加一行配置来加大该参数值。 目录 1.Server.xml配置…

有人真的会去分析代码吗

很早之前使用 webpack 的时候&#xff0c;也有类似的插件&#xff0c;分析打包出来之后的代码&#xff0c;分别是哪些模块比较庞大&#xff0c;针对打包的内容进行优化。说实话&#xff0c;知道归知道&#xff0c;但是没有哪个项目使用分析过。最近刚好看见了两个插件&#xff…

DOM的节点操作+事件高级+DOM事件流+事件对象

一.节点操作 1.父节点: node.parentNode 得到的是离元素最近的父级节点 2.子节点: parentNode.childNodes 所有的子节点 包含元素节点 文本节点等等parentNode.children (非标准) 获取所有的子元素节点,实际开发常用 parentNode.firstChild 获取…

clion run qt 问题汇总

一、Error copying file “D:/soft/QT/5.15.2/mingw81_64/bin/Qt5Cored.dll” to “D:/work/Ccode/qtproject/cmake-build-debug-qtmingw”.报错 查看路径下确实没有Qt5Cored.dll&#xff0c;只有Qt5Core.dll 注释掉cmakelist中的这三行 重新执行后成功 二、使用CLion编辑u…

前端探索之旅

目录 简介:内容大纲:第一章 前端开发简介1.1 前端开发的定义和作用1.2 前端开发的职责1.3 前端开发的技能要求1.4 前端开发的发展前景总结&#xff1a; 第二章 HTML基础2.1 HTML基本结构2.2 常见HTML标签和元素 第三章 CSS基础3.1 CSS基本语法3.2 常见CSS选择器3.3 常见CSS属性…

MySQL之 show profile 相关总结

MySQL之 show profile 相关总结 MySQL官网show profile介绍&#xff1a;https://dev.mysql.com/doc/refman/8.0/en/show-profile.html 1. 简介 show profile 和 show profiles 命令用于展示SQL语句的资源使用情况&#xff0c;包括CPU的使用&#xff0c;CPU上下文切换&#xf…

nvm下载node导致npm报错无法使用

有个依赖库需要更新下node&#xff0c;用nvm下载后项目跑不起来了&#xff0c;npm -v 还报错 其实一开始是npm下载不来&#xff0c;然后换了淘宝镜像后还是报错 然后就只能手动下载下了 进入node.js官网 https://nodejs.org/en/download 下载后注意要安装在你nvm目录中&#x…

windows安装apache-jmeter-5.6.2教程

目录 一、下载安装包&#xff08;推荐第二种&#xff09; 二、安装jmeter 三、启动jmeter 一、下载安装包&#xff08;推荐第二种&#xff09; 1.官网下载&#xff1a;Apache JMeter - Download Apache JMeter 2.百度云下载&#xff1a;链接&#xff1a;https://pan.baidu.…

【算法挨揍日记】day01——双指针算法_移动零、 复写零

283.移动零 283. 移动零https://leetcode.cn/problems/move-zeroes/ 题目&#xff1a; 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 …

Xcode升级导致关联库报错

想办法找到对应的库 然后到 Build Phases -- LinkBinary With Libraries中点击&#xff0c;选择对应的framework即可&#xff0c;就像我工程的报错 Undefined symbol: _OBJC_CLASS_$_ADClient _OBJC_CLASS_$_ASIdentifierManager 缺失的库是AdSupport.framework 添加后再次编…

【服务平台】Rancher运行和管理Docker和Kubernetes,提供管理生产中的容器所需的整个软件堆栈

Rancher是一个开源软件平台&#xff0c;使组织能够在生产中运行和管理Docker和Kubernetes。使用Rancher&#xff0c;组织不再需要使用一套独特的开源技术从头开始构建容器服务平台。Rancher提供了管理生产中的容器所需的整个软件堆栈。  完整软件堆栈 Rancher是供采用容器的团…

Git全栈体系(五)

第八章 IDEA 集成 GitHub 一、设置 GitHub 账号 如果出现 401 等情况连接不上的&#xff0c;是因为网络原因&#xff0c;可以使用以下方式连接&#xff1a; 然后去 GitHub 账户上设置 token。 点击生成 token。 复制红框中的字符串到 idea 中。 点击登录。 二、分享工程…

数据结构顺序表

今天主要讲解顺序表&#xff0c;实现顺序表的尾插&#xff0c;头插&#xff0c;头删&#xff0c;还有尾删等操作&#xff0c;和我们之前写的通讯录的增删查改有类似的功能。接下来让我们开始我们的学习吧。 1.线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特…

allegro中不可选时,如何对find进行可选操作

allegro出现不可选时&#xff0c;只能尝试其他单一的操作&#xff0c;但这样效率不高&#xff1b;可以通过菜单栏Display下拉菜单点击Element&#xff0c;即可实现FIND下选择需要调整的选项。