LeetCode Linked List Cycle II：找環入口節點

問題描述

給定單鏈表，返回環入口節點，無環返回 nullptr。要求 O(1) 空間。

數學原理

設：
- 入環前長度 a
- 環長 r
- 相遇點距入環口 b（順時針）
慢針走 a+b，快針走 a+b+kr (k≥1)。
速度比 1:2 → 2(a+b) = a+b+kr → a+b = kr → a = kr - b = (k-1)r + (r-b)。
即：從頭出發走 a 步，與從相遇點出發走 r-b 步到達同一位置（入環口）。

算法流程

1. 快慢指針找相遇點
2. 一指針 ptr1 = head，另一 ptr2 = meet
3. 同速（每次 1 步）前進，相遇點即為入環口

完整代碼

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return nullptr;
        ListNode *slow = head, *fast = head;
        bool hasCycle = false;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) { hasCycle = true; break; }
        }
        if (!hasCycle) return nullptr;
        ListNode *ptr1 = head, *ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        return ptr1;
    }
};

關鍵點

• 相遇後 不重置 fast，直接用 slow 作為 ptr2
• ptr1 從 head 出發，ptr2 從相遇點出發
• 同速前進，必在入環口相遇（證明見上）
• 時間 O(n)，空間 O(1)

直觀理解

相遇點到入環口的距離 = 頭到入環口的距離（模環長）。因此兩者同速出發，步數相等時必在入環口會合。

此題是快慢指針法的進階應用，掌握 a = (k-1)r + (r-b) 推導是關鍵。