⭐️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(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(节点/次)$，slow速度为$1(节点/次)$，环的节点数为$c$

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

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

slow入环后fast走的节点数是$(v_f\mathrm{m}\mathrm{o}\mathrm{d}c)t$，加上最初相隔的$l$减去fast跑的圈数就等于slow走的节点数$t-n_{2}c$

关系式如下：
$$(v_f\mathrm{m}\mathrm{o}\mathrm{d}c)t+l-n_{1}c=t-n_{2}c$$
$n_1、n_2$可以合并，化简得
$$(v_f\mathrm{m}\mathrm{o}\mathrm{d}c-1)t=nc-l$$
通过这个式子，我们就可以解释为什么fast每次走两步就必定可以相遇了。

把$v_f=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在这段时间内走过的节点数就是$\frac{n+k}{2}$，因为$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里的链表是顺序存储，那么找到下一个节点的地址比这个节点的地址低，就说明找到环的入口啦。

总结

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

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