LeetCode 141：環形鏈表——快慢指針判斷鏈表是否有環

題目描述

給定單鏈表頭節點，判斷鏈表中是否存在環。要求 O(1) 空間複雜度。

Floyd 判圈算法（快慢指針）

快指針 fast 每次移動 2 步，慢指針 slow 每次移動 1 步。若有環，兩者必在環內相遇；若 fast 到達 nullptr 則無環。

相遇證明：進入環後，相對速度為 1 步/輪，在長度為 L 的環上，最多 L 輪相遇。

C++ 實現

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

邊界處理

• 空鏈表、單節點無環：直接返回 false。
• 單節點自環（head->next == head）：循環條件 fast && fast->next 滿足，首輪即相遇返回 true。

複雜度

• 時間：O(n)，快指針最多走 2n 步。
• 空間：O(1)，僅兩指針。

總結

快慢指針是判斷鏈表環的經典解法，代碼簡潔、空間最優。掌握其相遇證明有助於舉一反三解決相關變體問題。