Q142 环形链表II

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

1 我的想法

最容易踩的坑：以为快慢指针第一次相遇就是答案。第一次相遇点不是环入口——相遇后还要从头再走一遍：让 cur（从 head 出发）和 fast（停在相遇点）同步各走 1 步，两者相遇的位置才是环入口。

2 简要回答

1. fast 每次 2 步、slow 每次 1 步，若 fast 或 fast->next 为空 → 无环，返回 null。
2. 第一次 fast == slow → 有环，记下相遇点。
3. cur = head，cur 与 fast 各走 1 步，直到 fast == cur → 返回该节点（环入口）。

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

3 为什么第一次相遇点不是入口

第一次相遇发生在环内，具体是环内哪个点取决于 a 和 b 的比例，没有任何规律保证它是入口。所以第二阶段必须有。

4 为什么第二轮双指针能在入口相遇

设 head→环入口距离为 a，环入口→第一次相遇点（沿前进方向）距离为 b，环长为 c。

相遇时（fast 走的路程是 slow 的 2 倍）：

1
2
3
4
5

slow 走：a + b
fast 走：2(a + b) = a + b + n·c     （fast 比 slow 多绕了 n 圈）

⇒  a + b = n·c
⇒  a = n·c - b

含义：

• 从 head 走 a 步 → 到达环入口；
• 从相遇点走 a 步 → 绕 n 圈后再退 b 步 → 也到达环入口。

所以 cur（head 出发）和 fast（相遇点出发）同步各走 1 步，恰好都在走 a 步后到达环入口，相遇。

5 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr) {
            if (fast->next == nullptr) {
                return nullptr;          // 无环
            }
            fast = fast->next->next;     // 走 2 步
            slow = slow->next;           // 走 1 步
            if (fast == slow) {          // 第一次相遇，说明有环
                ListNode* cur = head;
                while (fast != cur) {    // 同步走 1 步
                    cur = cur->next;
                    fast = fast->next;
                }
                return cur;              // 环入口
            }
        }
        return nullptr;                  // fast 走到末尾，无环
    }
};

用 1→2→3→4→5→(3)（3 是环入口，环长 3）验证：第一次相遇点在 5，第二阶段从 head 和 5 同步走，在 3 相遇 → 返回 3 ✓。

6 无环与空指针

• 无环：fast 先到末尾，fast == nullptr 退出循环，返回 null。
• 空链表 / 单节点：fast == nullptr 或 fast->next == nullptr，返回 null。
• fast->next->next 在 fast->next == nullptr 已排除的前提下是安全的（最多为 null，下一轮循环判断）。

7 易错点

• 第一次 fast == slow 直接 return 是错的：那只是环内某个点，不是入口。
• 第二阶段不需要判空：已确认有环，cur 和 fast 必然相遇。
• 无环判断必须覆盖 fast == nullptr 和 fast->next == nullptr 两种。
• 第一阶段别把 slow 写成走 2 步——快慢都走 2 步永远追不上。