LeetCode 142. 环形链表 II 解题思路与代码实现

为什么 n=1？（fast 必在 low 入环第一圈追上）

很多同学会疑惑 fast 是否会绕多圈才追上 low，答案是不会：

• 当 low 刚进入环时，fast 已经在环内，且两者的距离小于等于环的总长度 L；
• fast 每次比 low 多走 1 步，相当于以 1 步/次的速度追上 low；
• 最多需要 L 步就能追上，而 low 走 L 步刚好是环的一圈，因此 low 入环后第一圈内必被 fast 追上。

因此 n=1，代入公式继续化简：a + b = b + c → a = c（头结点到环入口的距离 = 相遇点到环入口的距离）。

第三步：定位环的第一个节点

基于 a = c 的核心结论，定位环入口：

1. 当快慢指针相遇后，将 fast 指针重新移回链表头结点；
2. 让 fast 和 low 指针以相同速度（每次走 1 步） 同时前进；
3. 当两者再次相遇时，所处的位置就是环的第一个节点。

算法复杂度

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

核心知识点

1. 快慢指针相遇 → 链表有环；
2. 相遇后 fast 回头结点，两指针同速前进 → 相遇点即为环入口。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return nullptr;
        
        ListNode* fast = head;
        ListNode* low = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            low = low->next;
            if (fast == low) break; // fast 和 low 相遇
        }
        
        if (fast != low) return nullptr;
        
        fast = head;
        while (fast != low) {
            fast = fast->next;
            low = low->next;
        }
        
        return fast;
    }
};