LeetCode 142：環形鏈表 II——尋找環入口節點的快慢指針法

題目描述

給定單鏈表頭節點，若存在環，返回環的入口節點；否則返回 nullptr。要求 O(1) 額外空間。

數學推導

設鏈表頭到環入口距離為 X，環長度為 Y。快指針 fast 每次走 2 步，慢指針 slow 每次走 1 步。兩者在環內相遇時：

• fast 走過 2t = X + mY + K
• slow 走過 t = X + nY + K
• 相減得 X + K = (m - 2n)Y，即 X = (m - 2n)Y - K

這說明：從頭節點出發走 X 步到達入口，與從相遇點繼續走 X 步（即繞環 m-2n 圈再退 K 步）到達同一節點。因此，相遇後令一指針回頭，另一保持，雙雙每次走 1 步，再次相遇點即為環入口。

算法流程

1. 快慢指針檢測是否有環，記錄相遇節點。
2. 若無環返回 nullptr。
3. 將一指針重置為 head，另一留在相遇點。
4. 兩指針同速前進，相遇節點即為入口。

C++ 實現

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

        ListNode *entry = head;
        while (entry != slow) {
            entry = entry->next;
            slow = slow->next;
        }
        return entry;
    }
};

邊界情況

• 空鏈表、單節點無環、單節點自環（head->next == head）。
• 環入口即為頭節點。

總結

快慢指針不僅能判斷有環，結合數學關係還能精確定位入口。畫圖輔助推導是解決鏈表環問題的關鍵技巧。