leet142.环形链表 II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

---

思路

朴素思路，可以

1. 用一个 hash 表记录节点的入度，由于头节点也可能时环的入口，所以要在前面加一个哨兵节点。第一次入度到达 2 的就是环的入口。
2. 或者更简单，用一个 hash set 记录每个节点是否被访问，第一个被访问两次的节点就是环的入口。

这样用了辅助空间，空间复杂度来到了 $O(n)$.

而题目就是让你用 $O(1)$ 空间解决。所以再进一步，我是想不到的。要用到一些数学计算。还是老朋友（链表常用技巧：快慢指针），定义两个指针 fast 和 slow。fast 每次走两步，slow 每次走一步。如果 fast 率先来到链表尾，说明无环。否则二者必然相遇（物理上来说 fast 相对于 slow 的速度为 1，再成环的链路上，必然追上 slow，也就是常说的套圈）。在有环的情况下，设从头节点到环入口需要走 $a$ 步，环中有 $b$ 个节点。

核心事实：快慢指针相遇时，slow 走了 $kb$ 步（也就是说 slow 走的步数是环中节点的整数倍）。参考灵神题解。

简单推导，设相遇时 fast 走了 $f$ 步，slow 走了 $s$ 步，由于 fast 的速度是 slow 的 2 倍，所以 $f=2s$。又因为 fast 比 slow 多走了 k 圈（扣掉从头到入环口的 $a$ 步），故有 $f-s=kb$，得 $s=kb$.

• fast = a + p
• slow = a + q

于是乎，相遇时 slow 相当于从入环口开始走了 $kb-a$ 步。因此，从相遇位置开始，再走 $a$ 步即可到达入环口。但我们不知道 $a$ 是多少，回想一下它的含义“从头节点到环入口需要走 $a$ 步”。因此，在相遇时设一个指针从头结点开始，slow 和它相遇时，它们都到达了入环口。

Code

Floyd 判圈法

上面第二中优化思路成为 Floyd 判圈法，又称龟兔赛跑算法。

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) { // 有环
            while (head != slow) { // 让head和slow一起走，相遇时即到达入环口
                head = head->next;
                slow = slow->next;
            }
            return head;
        }
    }
    return nullptr; // fast走到链表尾，说明无环
}

• 时间复杂度 $O(n)$
• 空间复杂度 $O(1)$

hash 表或集合辅助

// hash表记录入度
ListNode* detectCycle(ListNode* head) {
    // 记录每个节点的入度，head可能为入环口，因此前面加个哨兵，直接体现为初始化入度为1
    unordered_map<ListNode*, int> ingress_cnt = {{head, 1}};
    for (auto p = head; p; p = p->next) {
        if (++ingress_cnt[p->next] == 2) {
            return p->next;
        }
    }
    return nullptr;
}
 
// hash集合辅助
ListNode* detectCycle(ListNode* head) {
    unordered_set<ListNode*> visited;
    for (auto p = head; p; p = p->next) {
        if (visited.count(p)) return p;
        visited.insert(p);
    }
    return nullptr;
}

• 时间复杂度 $O(n)$
• 空间复杂度 $O(n)$

补充证明

为什么 fast 比 slow 多走了 k 圈？

相遇时，slow 走了 s 步，fast 走 2s 步。相遇说明 s 和 2s 相对于入环口的位置是相等的。从入环口开始算，fast 跑了 $2s-a$ 步，slow 跑了 $s-a$ 步。即，

$$2s-a\equiv s-a\mathrm{mod}b⟺s\equiv 0\mathrm{mod}b$$

所以相遇时，fast 比 slow 多走了 s 步，恰好是环长的整数倍。而 s 恰好又是 slow 走的步数！