141. Linked List Cycle

📘 題目敘述

給你一個 linked list 的頭節點 head，判斷這個 linked list 中是否存在 cycle。

如果 linked list 中存在某個節點可以再一次被走到（也就是沿著 next 指標走下去會回到之前出現過的節點），則該 linked list 存在 cycle。

內部用 pos 代表 tail 連回去的那個節點索引（0-based）。注意：pos 不會作為參數傳入。

如果 linked list 中存在 cycle，回傳 true；否則回傳 false。

條件限制

• linked list 的節點數量在範圍 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 介於 -1 到 n-1
• pos == -1 代表沒有 cycle

🧠 解題思路（一）直接改數字

這份寫法是用「改節點值當作走訪標記」來判斷是否走回來。

我用一個不會出現的數字 1000000 當成標記：

• 走訪每個節點時：
• 如果我發現某個節點的 val 已經被改成 1000000
  • 代表我之前走過這個節點，又回來了 → 一定有 cycle
• 否則我就把它的 val 改成 1000000，表示「這個節點我走過了」
• 然後繼續往 next 走

如果一路走到 nullptr，代表能走到尾巴且不會回到舊節點 → 沒有 cycle。

所有變數

• head：目前走訪到的節點指標（一路往後移）
• 1000000：我用來標記「走過」的特殊值

🪜 主要流程步驟

1. 從 head 開始一路往下走

• while (head)：只要還沒走到 nullptr 就繼續

2. 如果這個節點已經被標記過，代表有 cycle

• if (head->val == 1000000) return true;

3. 否則標記它，並前進到下一個節點

• head->val = 1000000;
• head = head->next;

4. 走到 nullptr 代表沒有 cycle

• return false;

💻 程式碼實作（一）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode* head) {
        while (head) {
            if (head->val == 1000000) {
                return true;
            }
            head->val = 1000000;
            head = head->next;
        }
        return false;
    }
};

🧠 解題思路（二）快慢指標

這題我使用的是經典的 快慢指標（Floyd Cycle Detection Algorithm）。

核心想法是：

如果鏈結串列中存在環，那麼一個走得快、一個走得慢的指標， 最後一定會在環內某個位置「相遇」。

反過來說：

• 如果鏈結串列沒有環
• 那快指標一定會先走到 nullptr
• 迴圈自然結束，代表沒有環

這個方法的好處是：

• 不需要額外空間
• 時間複雜度 O(n)，空間複雜度 O(1)

所有變數

• slow：慢指標，每次往前走 一步
• fast：快指標，每次往前走 兩步
• head：鏈結串列的起始節點

🪜 主要流程步驟

第一步：初始化快慢指標

• 一開始，slow 與 fast 都指向 head
• 代表兩個人從同一個起點出發

第二步：同步前進（關鍵）

只要滿足以下條件，就可以繼續走：

• fast != nullptr
• fast->next != nullptr

每一輪迴圈中：

• slow 往前走 1 步
• fast 往前走 2 步

slow = slow->next;
fast = fast->next->next;

第三步：判斷是否相遇

在每一輪移動後：

• 如果 slow == fast
• 代表快慢指標在某個節點相遇
• 一定存在環
• 立刻回傳 true

第四步：迴圈結束仍未相遇

如果跳出 while 迴圈，代表：

• fast 或 fast->next 為 nullptr
• 鏈結串列有尾端
• 不存在環

此時回傳 false

💡 為什麼這個方法一定正確？

• 若沒有環：
  • fast 會先走到 nullptr
  • 不可能與 slow 相遇
• 若有環：
  • fast 每輪比 slow 多走一步
  • 在環中相對距離會不斷縮小
  • 最終一定會在某個節點相遇

💻 程式碼實作（二）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;       // slow 走 1 步
            fast = fast->next->next; // fast 走 2 步
            if (slow == fast) {
                return true; // 在環中相遇
            }
        }
        return false;
    }
};

🔗 題目連結

https://leetcode.com/problems/linked-list-cycle/