/*
 * 演算法 / 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;
}