141. Linked List Cycle

題目 / Problem

中文：給定一個鏈結串列的頭節點 head，判斷這個串列裡面有沒有「環」。所謂「環」，就是沿著 next 指標一直往下走，會不會重新走回某個之前經過的節點。如果存在環，回傳 true；否則回傳 false。題目裡提到的 pos 只是用來說明尾節點接回哪個節點（出題者內部使用），並不會傳進函式裡，你看不到它。

English: Given head, the head of a linked list, determine whether the list contains a cycle. A cycle means that by repeatedly following the next pointer, you eventually arrive back at a node you have already visited. Return true if there is a cycle, otherwise false. The pos mentioned in the statement only describes (for the problem setter) which node the tail links back to — it is not passed to your function.

Constraints / 限制 - 節點數量範圍 / Number of nodes: [0, 10^4] - -10^5 <= Node.val <= 10^5 - pos 是 -1（無環）或一個合法索引 / pos is -1 (no cycle) or a valid index.

Worked example / 範例

Input:  head = [3,2,0,-4], pos = 1
Output: true

串列是 3 -> 2 -> 0 -> -4，而最後的 -4 的 next 又接回索引 1 的節點（值為 2），所以形成環，回傳 true。 The list is 3 -> 2 -> 0 -> -4, and the last node -4 points back to the node at index 1 (value 2), forming a cycle, so the answer is true.

名詞解釋 / Glossary

• 鏈結串列 / Linked list：一種資料結構，由一個個「節點」串起來。每個節點存一個值 val 和一個指向下一個節點的指標 next。最後一個節點的 next 通常是 NULL（空）。/ A chain of nodes; each node holds a value val and a pointer next to the following node. The last node's next is usually NULL.
• 節點 / Node：串列中的一個單位元素，這裡的型別是 struct ListNode。/ One element of the list, here of type struct ListNode.
• 指標 / Pointer：一個變數，存的不是資料本身，而是資料在記憶體中的「地址」。p->next 表示「跟著 p 的 next 指標走到下一個節點」。/ A variable that stores a memory address rather than the value itself. p->next means “follow p’s next pointer to the next node.”
• 環 / Cycle：串列中某個節點的 next 指回前面走過的節點，使得指標可以無限繞圈、永遠走不到 NULL。/ A node whose next points back to an earlier node, so following pointers loops forever and never reaches NULL.
• 雜湊表 / Hash set：一種能快速判斷「某個東西是否已經出現過」的容器，查詢與插入平均只要 O(1) 時間。/ A container that answers “have I seen this before?” in average O(1) time.
• 快慢雙指針 / Floyd's two pointers (tortoise and hare)：用兩個指標走串列，慢的一次走一步、快的一次走兩步。如果有環，快指標終究會從後面追上慢指標。/ Two pointers traversing the list: slow moves one step, fast moves two. If a cycle exists, fast will eventually catch up to slow.
• O(1) 額外空間 / O(1) extra memory：不論串列多長，演算法只額外用固定幾個變數，不隨輸入長度增加。/ The algorithm uses a fixed number of extra variables regardless of list length.

思路

最直覺的暴力做法是用一個雜湊表記錄「我走過哪些節點」。從 head 開始一個一個往下走，每到一個節點就先檢查它是否已經在雜湊表裡：如果在，代表我們繞回了走過的節點，就是有環；如果不在，就把它記下來再往前走。一直走到 NULL 還沒重複，就代表沒有環。這個做法正確又好懂，時間是 O(n)，但需要 O(n) 的額外空間來存所有節點。題目的進階要求是只用 O(1) 記憶體，所以我們想要更省空間的方法。關鍵觀察是：環就像一條跑道，如果有兩個人在上面跑、一個快一個慢，快的那個一定會在某一圈追上慢的那個（因為每走一步兩者距離縮短 1）。於是用「快慢雙指針」：慢指針一次走一步，快指針一次走兩步。若沒有環，快指針會先走到 NULL，回傳 false；若有環，兩個指針最後一定會指到同一個節點，回傳 true。這樣只用了兩個指標變數，空間是 O(1)。

The brute-force idea is to use a hash set to remember every node we have visited. Walk from head one node at a time; at each node, check whether it is already in the set. If it is, we have looped back to a node we saw before, so there is a cycle. If not, record it and move on. If we reach NULL without ever repeating, there is no cycle. This is correct and easy to understand — O(n) time — but it costs O(n) extra space to store all the nodes. The follow-up asks for O(1) memory, so we want something cheaper. The key insight is that a cycle behaves like a circular running track: if two runners go around it, one fast and one slow, the fast one must eventually lap and meet the slow one (each step closes the gap between them by one). This is Floyd's two-pointer (tortoise and hare) method: the slow pointer advances one node per step, the fast pointer advances two. If there is no cycle, the fast pointer hits NULL first and we return false. If there is a cycle, the two pointers are guaranteed to land on the same node, and we return true. We only ever use two pointer variables, so the space is O(1).

逐步走查 / Walkthrough

用範例 head = [3,2,0,-4]，且 -4 接回索引 1 的節點（值 2）。節點記為 A(3) -> B(2) -> C(0) -> D(-4)，而 D.next = B（形成環）。 Using head = [3,2,0,-4] where -4 links back to the node at index 1. Label nodes A(3) -> B(2) -> C(0) -> D(-4), with D.next = B (the cycle).

慢指針 slow 一次一步，快指針 fast 一次兩步，兩者都從 A 開始。每一輪先檢查快指針還能不能再走兩步（fast 和 fast->next 都不是 NULL）。 slow moves 1 step, fast moves 2 steps; both start at A. Each round we first check that fast can still take two steps.

第 3 步兩個指針相遇在 D，代表有環，回傳 true。注意若沒有環，fast 或 fast->next 會在某一步變成 NULL，迴圈結束、回傳 false。 At step 3 the pointers meet at D, proving a cycle, so we return true. If there were no cycle, fast or fast->next would become NULL and the loop would end, returning false.

Solution — C

/*
 * 演算法 / Algorithm: Floyd 快慢雙指針 (tortoise & hare)。
 * slow 每次走 1 步, fast 每次走 2 步。有環則兩者必相遇; 無環則 fast 先到 NULL。
 * slow advances 1 node, fast advances 2. They meet iff a cycle exists; otherwise fast hits NULL.
 * Time O(n), Space O(1).
 */

// LeetCode 已預先定義好節點結構, 這裡只是說明它長什麼樣 (實際不必重寫)。
// LeetCode predefines the node struct; shown here only for clarity.
struct ListNode {
    int val;                 // 節點存的值 / the value stored in this node
    struct ListNode *next;   // 指向下一個節點的指標 / pointer to the next node
};

bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;  // 慢指針從頭開始 / slow pointer starts at head
    struct ListNode *fast = head;  // 快指針也從頭開始 / fast pointer starts at head too

    // 只要 fast 還能安全往前走兩步就繼續 (避免對 NULL 取 ->next 而崩潰)。
    // Loop while fast can still take two steps; guards against dereferencing NULL.
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;        // 慢指針前進 1 步 / slow moves one node forward
        fast = fast->next->next;  // 快指針前進 2 步 / fast moves two nodes forward

        // 若兩指針指到同一個節點, 代表 fast 從後面追上了 slow → 有環。
        // If both pointers reference the same node, fast caught slow → cycle exists.
        if (slow == fast) {
            return true;          // 回傳「有環」/ return true: a cycle is present
        }
    }

    // 迴圈正常結束代表 fast 走到了 NULL, 串列有盡頭 → 無環。
    // Falling out of the loop means fast reached NULL: the list ends → no cycle.
    return false;
}

Solution — C++

/*
 * 演算法 / Algorithm: Floyd 快慢雙指針 (tortoise & hare)。
 * slow 走 1 步、fast 走 2 步; 有環必相遇, 無環 fast 先到 nullptr。
 * slow steps by 1, fast by 2; they meet iff there is a cycle, else fast reaches nullptr.
 * Time O(n), Space O(1).
 */

// LeetCode 預先定義的節點結構 (此處僅供參考) / Node struct predefined by LeetCode (shown for reference).
struct ListNode {
    int val;            // 節點的值 / the node's value
    ListNode *next;     // 指向下一節點 / pointer to the next node
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;  // 慢指針 / slow pointer, starts at head
        ListNode *fast = head;  // 快指針 / fast pointer, starts at head

        // nullptr 是 C++ 表示「空指標」的關鍵字。確認 fast 能再走兩步才進迴圈。
        // nullptr is C++'s null-pointer keyword. Enter the loop only if fast can move twice.
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;        // 慢指針前進 1 / advance slow by one
            fast = fast->next->next;  // 快指針前進 2 / advance fast by two

            // 指標相等代表指向同一節點 (同一個記憶體地址) → 有環。
            // Equal pointers mean the same node (same address) → a cycle exists.
            if (slow == fast) {
                return true;          // 有環 / cycle found
            }
        }

        // fast 走到 nullptr, 串列有結尾 → 無環。
        // fast reached nullptr, so the list terminates → no cycle.
        return false;
    }
};

複雜度 / Complexity

• Time: O(n) — n 是節點數。沒有環時, fast 最多走過全部節點 (約 n/2 輪) 就到 NULL；有環時, slow 進入環後最多再繞一圈 fast 就追上, 仍是線性。主要花費就是這趟走訪。/ n is the number of nodes. Without a cycle, fast reaches NULL after about n/2 steps; with a cycle, fast catches slow within roughly one extra loop. The traversal dominates, so it is linear.
• Space: O(1) — 只用了 slow 和 fast 兩個指標變數, 與串列長度無關, 不隨 n 增長。/ Only two pointer variables are used, independent of the list length — constant extra memory.

Pitfalls & Edge Cases

• 空串列 / Empty list (head == NULL)：迴圈條件 fast != NULL 第一次就是假, 直接回傳 false, 不會崩潰。/ The loop condition fast != NULL is false immediately, so we correctly return false without crashing.
• 快指針的 NULL 檢查順序 / Order of the fast-pointer null checks：必須先確認 fast != NULL 再 看 fast->next。若反過來, 當 fast 已是 NULL 時去取 fast->next 會存取非法記憶體而當機。&& 的短路特性保證左邊為假時右邊不會執行。/ Check fast != NULL before fast->next; otherwise dereferencing a NULL fast crashes. && short-circuits, so the right side is skipped when the left is false.
• fast 一次走兩步, 不是一步 / fast must move two, not one：若兩個指針都一次走一步, 它們永遠保持相同距離、就算有環也不會相遇。速度差 1 才能保證追上。/ If both pointers moved by one, they'd stay the same distance apart and never meet even in a cycle. The speed difference of 1 guarantees they converge.
• 不要比較節點的值 / Don't compare values, compare pointers：判斷相遇要用 slow == fast（同一個節點/地址）, 不是 slow->val == fast->val。不同節點可能有相同的值, 會造成誤判。/ Use pointer identity slow == fast, not slow->val == fast->val — distinct nodes can share a value and cause false positives.
• 單一節點且無環 / Single node, no cycle ([1], pos=-1)：fast->next 為 NULL, 迴圈不執行, 回傳 false, 正確。/ fast->next is NULL, the loop body never runs, and we return false — correct.