环形链表 [两道题目]（详解）

本文主要是介绍环形链表 [两道题目]（详解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

环形链表（详解）

第一题：

题目：

题目链接

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路：

首先我们创建一个快慢指针，让其在链表内不断走，如果链表是带环的，那么快指针迟早会追上慢指针，追上了那就是带环链表。

但是注意了在这里

我们的快慢指针之间的速度差距一定得是——fast = 2slow，即是慢指针走1步，快指针走两步。

为什么呢？

我们假设slow指针进入环时离fast指针的距离是X。

当X == 0的时候，slow一进环就碰到fast了，说明第一个节点到环的长度和环内的长度是一样的。
如果slow走到环的长度是，环内的一半长度，这个时候，slow进环的时候，fast刚好在环中间。如图所示

也就是说，当slow慢指针入环之后，fast和slow每走一次，他们之间的距离X都会-1.如图所示

其实就证明了，slow入环之后，和fast的距离是X，slow再走X次，fast就能追上slow指针。

那为什么说fast只能是slow的两倍速率呢？

因为如果我们的fast走其他步比如3步 4步，就有可能会不相遇！

如图所示，如果X是奇数，比如是1，那么一次走三步就会直接跳过去，那么此时的X就会重置为环的长度-1，如果这个新的X也是奇数，那么就会死循环！

fast走其他步也是同样的道理，这里就不在例举。

因此其他步总有一些特殊的情况无法处理，无法相遇。

但是如果fast每次走两步，每次的距离减少1 那就一定会相遇。

因此这里只能让fast = 2slow。

慢指针在环内是走不到一圈的，严格来说，最差的情况是slow在入环第一个节点，fast在入环第二个节点，这个时候慢指针走接近2/3圈就会被追上。

代码实现：

struct ListNode 
{int val;struct ListNode* next;
};typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head)
{// 创建快慢指针ListNode* slow, * fast;slow = fast = head;// 快慢指针都在环里面一直走下去，快指针迟早能追上慢的指针while (fast && fast->next) // 我们不知道传进来的链表是不是带环的因此，fast和fast->next 都不能为NULL{slow = slow->next;fast = fast->next->next; // 注意了这里的快指针只能是 fast = 2slow // 如果快指针追上慢指针那就是带环if (fast == slow)return true;}// 走到这里说明 不带环 return false;
}

第二题：(难度：中等)

题目：

题目链接

如果链表中有某个节点，可以通过连续跟踪 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
解释：链表中没有环。

思路：

思路1：（理解容易，写起来较麻烦）

创建快慢指针，如果有环就相遇，无环无法相遇
首先让fast和slow相遇，找到这个相遇的节点。
然后把相遇的节点断开
然后相遇点和到相遇点的上一个节点是一个链表，一开始的链表头到断点也是一个链表。
这个时候我们把问题转化成了两个链表的相交问题，找到交点，这个交点就是题目要找的入环的第一个节点！

代码实现：

struct ListNode 
{int val;struct ListNode* next;
};typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{// 排除空链表的情况if(head == NULL)return NULL;// 创建快慢指针ListNode* slow, *fast;slow = fast = head;// 让快慢指针遍历链表，看看带环while(fast && fast->next){slow = slow->next;fast = fast->next->next;// 判断是否有相遇点if(slow == fast)break;}// 排除不带环的情况if(slow != fast)return NULL;// 让相遇点断开 ListNode* next = slow->next; // 让next存储相遇点的下一个节点slow->next = NULL; // 断开相遇点// 这个时候next 和 head 分别为两条链表// 这个时候我们就找这两个链表的相交点就好了，交点就是入环第一个节点// 要想找到交点首先要求两个链表的长度ListNode* curhead = head;ListNode* curnext = next;int lenhead = 0;int lennext = 0;// 遍历head链表，统计长度while(curhead){lenhead++;curhead = curhead->next;}// 统计next链表长度while(curnext){lennext++;curnext = curnext->next;}// 默认head为起始点的为长链表 next为起始点的为短链表ListNode* longlist = head;ListNode* shortlist = next;// 判断两个链表的长度是否和我们默认的情况相同if(lenhead < lennext){   // 不同就改过来longlist = next;shortlist = head;}// 计算两个链表的长度差int gap = abs(lenhead - lennext);// 让长链表走两个链表的长度差while(gap--){longlist = longlist->next;}// 这个时候长短链表的长度相同了while(longlist){// 这个时候要判断next指向的是否是入环的第一个节点，因为快慢指针的相遇点可能是入环的最后一个节点// 因此要先判断是否为交点if(longlist == shortlist)return longlist;// 让两个链表都向后走longlist = longlist->next;shortlist = shortlist->next;}// 如果走到这里就说明有情况没有排除// 比如链表只有一个节点且不带环return NULL;
}

思路2：（理解较难，写起来比较容易）

注意思路2一定要知道推论是怎么推出来的，要理解透彻代码是怎么来的！

首先找通过快慢指针找到相遇点。
我们假设第一个节点到入环的第一个节点的距离叫做L，把slow指针入环后走的距离叫X，环的长度是C。如图所示
那么慢指针走的距离就是：L + X (慢指针在环内一定走不过一圈)
快指针走的距离就是： L + N * C + X (N代表走的环的圈数)

如果L短C大也就是环的长度大那么N就小，就是快指针绕环走的圈数少

如果L长C小，也就是环的长度小，N就大，就是快指针要绕环走很多圈，慢指针才能入环。

如图所示，L长C小的情况，N会比较大

我们又知道 2slow = fast 也就是2(L + X) = L + N*C + X
推论得知 L = N*C - X. 也就是第一个节点到入环的第一个节点的距离L = 快指针在环内走的长度N * C 再减去一个慢指针入环的距离 X

也可以理解成 L = （N-1） C + C - X*

也就是fast走了（N-1）* C 的距离后再走了一个 C - X的距离就是L的长度

也就是说从相遇点有一个指针，和链表的起始点开始一起走，两个指针相遇的节点就是我们要找的入环的第一个节点

代码实现：

struct ListNode 
{int val;struct ListNode* next;
};typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{// 首先创建快慢指针ListNode* slow, *fast;slow = fast = head;// 通过快慢指针判断是否带环,并且让slow和fast相遇时就退出while(fast && fast->next){slow = slow->next;fast = fast->next->next;// 如果相遇就退出if(slow == fast)break;}// 走到这里有可能时slow == fast 也有可能链表不是带环链表// 传入空链表的情况也要排除// 如果链表只有一个节点且不自身成环的情况要排除if(fast == NULL || fast->next == NULL) // 排除不是带环链表的情况return NULL;// 让相遇点和链表起始点同时开始走，当两个指针相遇的时候，这个节点就是入环的第一个节点// 注意！这里是一个推论，切记不可不知道推论怎么来的！ // 推论详解  看自己的笔记或者博客。博客地址：ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}// 走到这里meet和head指向的节点就是入环的第一个节点return meet;
}