首页 > 其他分享 >142. 环形链表 II

142. 环形链表 II

时间:2024-09-08 19:53:30浏览次数:14  
标签:II slow 142 fast next 链表 节点 指针

给定一个链表的头节点  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
解释:链表中没有环。

题解

对于链表找环路的问题,有一个通用的解法—— 快慢指针( Floyd 判圈法) 。给定两个指针,分别命名为 slow 和 fast ,起始位置在链表的开头。每次 fast 前进两步, slow 前进一步。如果 fast可以走到尽头,那么说明没有环路;如果 fast 可以无限走下去,那么说明一定有环路,且一定存 在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时,我们将 fast 重新移动到链表开头,并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时,相遇的节点即为环路的开始点。
双指针的第一次相遇:
设两指针 fast,slow 指向链表头部 head 。
令 fast 每轮走 2 步,slow 每轮走 1 步。
执行以上两步后,可能出现两种结果:

第一种结果: fast 指针走过链表末端,说明链表无环,此时直接返回 null。

如果链表存在环,则双指针一定会相遇。因为每走 1 轮,fast 与 slow 的间距 +1,fast 一定会追上 slow 。

第二种结果: 当fast == slow时, 两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系:

设链表共有 a+b 个节点,其中 链表头部到链表入口 有 a 个节点(不计链表入口节点), 链表环 有 b 个节点(这里需要注意,a 和 b 是未知数,例如图解上链表 a=4 , b=5);设两指针分别走了 f,s 步,则有:

fast 走的步数是 slow 步数的 2 倍,即 f=2s;(解析: fast 每轮走 2 步)
fast 比 slow 多走了 n 个环的长度,即 f=s+nb;( 解析: 双指针都走过 a 步,然后在环内绕圈直到重合,重合时 fast 比 slow 多走 环的长度整数倍 )。
将以上两式相减得到 f=2nb,s=nb,即 fast 和 slow 指针分别走了 2n,n 个环的周长。

接下来该怎么做呢?

如果让指针从链表头部一直向前走并统计步数k,那么所有 走到链表入口节点时的步数 是:k=a+nb ,即先走 a 步到入口节点,之后每绕 1 圈环( b 步)都会再次到入口节点。而目前 slow 指针走了 nb 步。因此,我们只要想办法让 slow 再走 a 步停下来,就可以到环的入口。

但是我们不知道 a 的值,该怎么办?依然是使用双指针法。考虑构建一个指针,此指针需要有以下性质:此指针和 slow 一起向前走 a 步后,两者在入口节点重合。那么从哪里走到入口节点需要 a 步?答案是链表头节点head。

双指针第二次相遇:
令 fast 重新指向链表头部节点。此时 f=0,s=nb 。
slow 和 fast 同时每轮向前走 1 步。
当 fast 指针走到 f=a 步时,slow 指针走到 s=a+nb 步。此时两指针重合,并同时指向链表环入口,返回 slow 指向的节点即可。

 

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast,*slow;
        fast=slow=head;
        do{
            if(!fast || !fast->next)
                return nullptr;
            fast=fast->next->next;
            slow=slow->next;
        }while(fast!=slow);

        fast=head;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};

标签:II,slow,142,fast,next,链表,节点,指针
From: https://blog.csdn.net/qq_33811080/article/details/141896914

相关文章

  • Day07 字符串part01| LeetCode 344. 反转字符串,541. 反转字符串II,卡码网:54.替换数字
    反转字符串344.反转字符串classSolution{publicvoidreverseString(char[]s){intlens=s.length;intright,left;if(lens%2!=0)//奇数个{right=lens/2+1;left=lens/2-1......
  • Day03 链表part01| LeetCode 203. 移除链表元素,707. 设计链表,206. 反转链表
    链表理论基础链表一种通过指针串联在一起的线性结构数据域指针域(存放指向下一个节点的指针,最后一个节点的指针域指向NULL)入口节点——head头节点链表类型单链表双链表两个指针域一个指向下一个节点一个指向上一个节点循环链表首尾相连约瑟夫环问题......
  • Day04 链表part02| LeetCode 24. 两两交换链表中的节点,19. 删除链表的倒数第 N 个,160.
    两两交换链表中的节点24.两两交换链表中的节点classSolution{publicListNodeswapPairs(ListNodehead){//设置虚拟头节点ListNodedummy=newListNode(0,head);ListNodecur=dummy;while(cur.next!=null&......
  • 20240911_220441 公共基础 线性链表
    什么是线性链表单向线性链表双向线性链表带链的栈带链队列线性链表的运算循环链表考点小结习题c习题a习题b习题c......
  • LeetCode //C - 350. Intersection of Two Arrays II
    350.IntersectionofTwoArraysIIGiventwointegerarraysnums1andnums2,returnanarrayoftheirintersection.Eachelementintheresultmustappearasmanytimesasitshowsinbotharraysandyoumayreturntheresultinanyorder. Example1:......
  • 数据结构基础讲解(三)——线性表之循环链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e数据结构基础讲解(二)——线性表之单链表专项练习-CSDN博客 个人主页:樱娆π-CSDN博客目录循环链表双向链表......
  • 003——单链表
    1.链式存储的特点逻辑(通过指针实现)上相邻,物理上可相邻可不相邻2.结点(节点都可以)4(&8)8(&6)6(&1)1(&9)9(NULL)4后面存上8的地址8后面存上6的地址6后面存上1的地址1后面存上9的地址9后面存上空地址也就是说,在链表中,需要存储:数据本身+下一个数据的地址,大体结构如下:数......
  • 【数据结构】单链表专题
    链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车......
  • 数据结构基础讲解(二)——线性表之单链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e 上一节我讲了线性表中顺序表的定义以及常用的算法,那么这节我将继续讲解顺序表中的链式结构以及常见的算法。数据......
  • Java毕设项目II基于Spring Boot+Vue的失物招领平台
    目录一、前言二、技术介绍三、系统实现四、论文参考五、核心代码六、源码获取全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者,专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末一、前言在快节奏的生活中,物品遗失与寻回成为了人......