文章目录

• ⭐️[142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
• 思路
• • 哈希表
  • 双指针
  • 双指针（优化）
  • • 为什么fast每次走2步？
    • 环找到了，那么环入口呢？
  • 投机取巧
• 总结

⭐️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解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 10⁴] 内
• -10⁵ <= Node.val <= 10⁵
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路

哈希表

最简单的方法就是遍历链表，把每个节点的地址都存进哈希表，遇到相同的就说明有环并且找到了入环的第一个节点。

class Solution {public:    ListNode *detectCycle(ListNode *head) { unordered_set<ListNode*> record; while (head != NULL) {     if (record.find(head) != record.end()) {  return head;     }     record.insert(head);     head = head->next; } return NULL;    }};

时间复杂度：$O(n)$

空间复杂度：$O(n)$

双指针

指针fast每次只走一步，用step1记录步数。

fast每走一步，slow都从头开始走，用step2记录步数。

当slow走到fast位置时，若二者步数不同，说明有环，此时这个位置就是入环节点。

class Solution {public:    ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; int step1 = 0, step2 = 0; while (fast != NULL) {     fast = fast->next;     step1++;     slow = head;     step2 = 0;     while (slow != fast) {  slow = slow->next;  step2++;     }     if (step2 != step1) {  return fast;     } } return NULL;    }};

因为每次slow都从头开始走，时间复杂度太大了，不过这种方法在LeetCode上还是能过的。

时间复杂度： O ( n 2 ) O(n^2) O(n2)

空间复杂度：$O(1)$

双指针（优化）

依然是两个指针，但都从头开始，fast指针每次走2步，slow指针每次走1步。

fast与slow重合，说明链表有环。

为什么fast每次走2步？

那么问题来了，因为指针不是连续走，而是跳着走，如果链表有环，那么两个指针一定会相遇重合吗，fast不会总是跳过slow吗？fast每次走3步4步呢？

slow第一次走到环入口时，fast的位置可以在环内任意节点处，这取决于环外节点的数量。

通过实验发现：

如果fast每次走2步，两指针都入环后，fast和slow的距离是一步一步缩短的，所以必然相遇重合。

如果fast每次走3步，两指针都入环后，如果环节点数是偶数，两指针相隔节点数是奇数，那么无法相遇。

如果fast每次走4步，两指针都入环后，如果环节点数是偶数，两指针相隔节点数是奇数，那么无法相遇。

实验方法不准，但是可以发现是否能相遇不但和fast的速度、入环后两指针的间隔有关，还和环节点数有关。

下面通过数学推导一下：

假设fast速度为 v f ( 节 点 / 次 ) v_f(节点/次) vf​(节点/次)，slow速度为$1(节点/次)$，环的节点数为$c$

注意到如果 v f = 5 v_f=5 vf​=5，环长$c=3$，那么 v f = 2 v_f=2 vf​=2和 v f = 5 v_f=5 vf​=5是没有区别的。也就是说只要考虑 v f v_f vf​的数值比$c$小的情况，即 v f m o d    c v_f\mod c vf​modc

假设最终能够相遇，slow指针刚入环时两指针相隔$l(0⩽l<c)$，之后走了$t$次，两指针走的完整的圈数分别 n 1 、 n 2 n_1、n_2 n1​、n2​

slow入环后fast走的节点数是 ( v f m o d    c ) t (v_f\mod c)t (vf​modc)t，加上最初相隔的$l$减去fast跑的圈数就等于slow走的节点数 t − n 2 c t-n_2c t−n2​c

关系式如下：
(vf mod    c ) t + l −n1 c = t −n2 c (v_f\mod c)t+l-n_1c=t-n_2c (vf​modc)t+l−n1​c=t−n2​c
n 1 、 n 2 n_1、n_2 n1​、n2​可以合并，化简得
(vf mod    c − 1 ) t = n c − l (v_f\mod c-1)t=nc-l (vf​modc−1)t=nc−l
通过这个式子，我们就可以解释为什么fast每次走两步就必定可以相遇了。

把 v f = 2 v_f=2 vf​=2代入，若$c>2$，得$t=nc-l$ ，可以发现对任意$c$和$l(0⩽l<c)$都有$t$和$n$使等式成立，故必定可以相遇。

若$c=1$，因为$0⩽l<c$所以$l=0$，说明slow一进环就和fast相遇了，这和我们的实验一致。

若$c=2$，$l$可能为0或1，$l$为0的不用说，那么$l=1$，得$-t=2n-1$，此时只有$n=0,t=1$可以满足，也就是说环节点数为2，slow入环后两指针相差1个节点的情况下，只要再走一次就可以相遇，也和我们的实验一致。

综上，fast每次走2步必定可以和slow相遇。

那么fast每次走3步呢，举个例子，如果环节点数是4，两指针相隔1，带入得2t=4n-1，显然，等式不可能成立，故无法相遇。

如果fast每次走4步，看下$c>4$的情况，$3t=nc-l$ ，如果$c=6$，$l=1$，那么等式不可能成立，即不会相遇，把$l$改成$3$呢？等式又可以成立了，说明会相遇了。通过实验验证也没有问题。

注：因为网上的题解都是直接说fast每走两步必定相遇，没有解释为什么3步，4步不行的。所以这个式子完全是我自己推出来的，正确性有待考究。我自己也试验了很多例子暂没有发现错误。如有思路问题或者错误还请各位大佬指正。

环找到了，那么环入口呢？

如图所示，假设环外节点数为$a$，环入口按顺序到快慢指针相遇位置节点数为$b$，从相遇位置按顺序到环入口节点数为$c$。

要求节点入口，只要知道a是多少，然后从头遍历就可以了。

首先，slow刚入环时fast可以在环的任意位置，设环长为$n$，fast下下次走到环入口时经过的节点数为$n+k$，那么slow在这段时间内走过的节点数就是n+k 2 \frac{n+k}{2} 2n+k​，因为$k⩽n$ ，所以slow最多只能走一圈，而fast却已经走了一圈多。所以slow在入环后的第一圈内必定和fast相遇。

那么相遇时，slow走了$a+b$个节点，fast走了$a+b+n(b+c)$个节点，$n$表示圈数。

slow每走一个节点，fast走两个，那么有：
$$2(a+b)=a+b+n(b+c)$$
两边消掉一个$(a+b)$，
$$a+b=n(b+c)$$
因为要求a，那么移项，
$$a=n(b+c)-b$$
提出一个$(b+c)$，
$$a=(n-1)(b+c)+c$$
我们发现，a就等于n-1个环加上c。

因此，我们可以定义一个指针ptr从头开始遍历，slow从现在的位置和它一起遍历，最后两者相遇处就是环的入口。

class Solution {public:    ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast != NULL && fast->next != NULL) {     slow = slow->next;     fast = fast->next->next;     if (slow == fast) {  ListNode* ptr = head;  while (ptr != slow) {      ptr = ptr->next;      slow = slow->next;  }  return ptr;     } } return NULL;    }};

时间复杂度：$O(n)$

空间复杂度：$O(1)$

投机取巧

上面的数学推导太枯燥了，最后来个好玩的娱乐一下。

class Solution {public:    ListNode *detectCycle(ListNode *head) { while (head != NULL) {     if (head->next <= head) {  return head->next;     }     head = head->next; } return NULL;    }};

据说LeetCode里的链表是顺序存储，那么找到下一个节点的地址比这个节点的地址低，就说明找到环的入口啦。

总结

这道题对链表，双指针，数学能力都是很大的考验。

我把能想到的，收集到的都写在这里了，可以说是够详细了吧，还希望各位多多三连支持🙏