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