LeetCode Linked List Cycle：快慢指針檢測環

題目

判斷單鏈表是否有環。進階：O(1) 空間。

方法一：HashSet 記錄訪問節點

遍歷鏈表，用 unordered_set 存地址。遇到重複地址 → 有環。時間 O(n)，空間 O(n)。

方法二：快慢指針 (Floyd 判圈算法)

慢指針每次 1 步，快指針每次 2 步。若有環，快慢指針必相遇（相對速度 1 步/輪，環長 L，最多 L 輪相遇）。無環則快指針先到 null。時間 O(n)，空間 O(1)。

代碼 (C++)

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

延伸：找環入口

相遇後，將一指針移回 head，兩指針同速前進，再次相遇處即環入口。證明：設頭到入口 a，入口到相遇點 b，環長 L。相遇時慢指針走 a+b，快指針走 a+b+kL = 2(a+b) ⇒ a+b = kL ⇒ a = kL-b。從頭走 a 步到入口，從相遇點走 a 步 (即 kL-b) 也到入口。