本文共 1746 字，大约阅读时间需要 5 分钟。

面试题 02.08. 环路检测

难度中等

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 1：

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

输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

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

输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

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

输出：no cycle 解释：链表中没有环。

进阶：

你是否可以不用额外空间解决此题？

思路1.0（已看题解）：

---

如果链表中有环，那么快慢指针就一定可以相遇（且一定再环上，如图上的c点），此时快指针移动过的距离是慢指针的2倍，根据图中的参数，我们可以写出以下等式：

(m+y) * 2=m+xn+y //这里的xn是当相遇时快指针已经在环上循环了x次，x>=1且为整数

=> m+y=xn => m=n-y+(x-1) * n //下面解释为什么写成这种形式

接下来将快指针置于表头(此时快指针在a处，慢指针在c处)，与慢指针以相同速度在链表上移动，当快指针移动到b处时，移动了m的距离，根据上面的等式可知，慢指针移动了n-y+(x-1) * n的距离。

我们来分析一下此时的慢指针在什么位置：

先移动(x-1) * n的距离，相当于在环上循环了(x-1)次，慢指针又回到了c点，然后再移动n-y的距离，如图所示，n-y正好是c点到b点的距离，说明此时慢指针也移动到了b点，即快慢指针在环路的开头节点相遇了。

作者：chen-hui-d

链接：https://leetcode-cn.com/problems/linked-list-cycle-lcci/solution/kuai-man-zhi-zhen-zheng-ming-bi-jiao-yan-jin-by-ch/

---

（1）用数学公式推导出m+y = x * n =>m = 1*n + (x-1) * n - y => m = n - y

（2）此时已得到了快慢指针在循环部分中相遇于C点，因为 m = n - y，所以此时让一个指针从相遇点C出发，一个指针从起点A出发，两人经过相同的距离会在循环开头部分B处相遇，因为 m = n - y

代码1.0：

class Solution {
   public:    ListNode* detectCycle(ListNode* head) {
           if (!head || !head->next) return NULL;                ListNode* fastP = head;        ListNode* slowP = head;        while (fastP && fastP->next) {
               fastP = fastP->next->next;            slowP = slowP->next;            //如果有循环部分，快满指针于此处相遇            if (fastP == slowP) break;        }        //没有循环部分        if (fastP != slowP) return NULL;                fastP = head;        //头节点重新出发的指针，于上述相遇点出发的指针，将通过相同的距离于循环首部相遇        while (fastP != slowP) {
               fastP = fastP->next;            slowP = slowP->next;        }        return slowP;    }};

画图模拟行为推导数学公式。。。我不配

加粗样式

转载地址：http://wvowi.baihongyu.com/