題目 141：「環形鏈結 (Linked List Cycle)」 是一道經典的鏈結串列問題，目標是判斷一個單向鏈結串列是否包含環（cycle）。環形鏈結是指在鏈結串列中，某個節點的 next 指向了前面的一個節點，形成了一個迴圈結構。

題目：

給定一個鏈結串列的頭節點，請判斷該鏈結串列中是否有環。

範例：

1. 輸入：head = [3,2,0,-4]，環的位置在節點 1（即節點值為 2 的地方）。

   • 輸出：true（表示鏈結串列中有環）

2. 輸入：head = [1,2]，環的位置在節點 0（即節點值為 1 的地方）。

   • 輸出：true

3. 輸入：head = [1]，沒有環。

   • 輸出：false

解題思路

直觀的解法是使用 hash table 來記錄我們遍歷過的節點。如果遇到一個節點之前已經遍歷過，則說明鏈結串列中有環。

實作：

/**
 * 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) {
        unordered_map<ListNode *, int> map;
        ListNode *curr = head;
        while (curr != nullptr) {
            if (map.count(curr)) {
                return true;
            }
            map[curr] = 1;
            curr = curr->next;
        }
        return false;
    }
};

其實不用用到 key value 的 hash table，因為用不到 value，可以改用 unordered_set 也可以，

實作：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> set;
        ListNode *curr = head;
        while (curr != nullptr) {
            if (set.count(curr)) {
                return true;
            }
            set.insert(curr);
            curr = curr->next;
        }
        return false;
    }
};

另一種解法是雙指標法也叫做快慢指標，核心思想是使用兩個指標，快指標一次走兩步，慢指標一次走一步，假如快指標走到某步發現跟慢指標一樣(相遇)，則表示該鏈結串列是個環形，如果不是環形的話，那麼快指標會先到達鏈結串列的末端(nullptr)。

實作：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) // 鏈結串列為空，沒有環
            return false;
        if (head->next == nullptr) // 鏈結串列只有一個節點，沒有環
            return false;

        ListNode *slow = head;
        ListNode *fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            if (slow == fast) { // 快慢指標相遇，表示有環
                return true;
            }
            slow = slow->next; // 慢指標移動一步
            fast = fast->next->next; // 快指標移動兩步
        }
        return false;
    }
};

順便練習遞迴版本，

實作：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) // 鏈結串列為空，沒有環
            return false;
        if (head->next == nullptr) // 鏈結串列只有一個節點，沒有環
            return false;

        ListNode *slow = head;
        ListNode *fast = head->next;
        return traverse(slow, fast);
    }
private:
    bool traverse(ListNode *slow, ListNode *fast) {
        if (fast == nullptr || fast->next == nullptr) {
            return false;
        }
        if (slow == fast) { // 快慢指標相遇，表示有環
            return true;
        }
        slow = slow->next; // 慢指標移動一步
        fast = fast->next->next; // 快指標移動兩步
        return traverse(slow, fast);
    }
};

參考：
#141. Linked List Cycle