142. 环形链表 II

难度：🟡 Medium | 标签：链表、快慢指针 | 状态：⬜ LeetCode 链接

思路

Floyd 算法：

1. 快慢指针找到相遇点
2. 一指针从 head，一从相遇点，同速走，再次相遇即环入口

数学：head 到入口距 a，入口到相遇点距 b，相遇点回入口距 c。2(a+b) = a+b+k(b+c) ⇒ a = (k-1)(b+c) + c，所以从 head 走 a 步等于从相遇点走 c 步（+ 整圈）。

代码

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

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 第二阶段两指针同速，不是快慢
• 一定要会推 a = c 的数学证明（高频追问）
• 无环：fast 先到 nullptr，返回 nullptr