題目網址：https://leetcode.cn/problems/linked-list-cycle/

題意：判斷 linked list 中是否有 cycle。

Solution：

想法：利用兩個不同步長的 ptr, slow 每次只走一步, 而 fast 每次走兩步

  • 若存在循環, 則 slow 和 fast 必相遇（fast 倒追 slow）
  • 若不存在循環, fast 必先抵達 nullptr
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        // 判斷 fast, 因為若沒有 cycle, fast 會比較快抵達 nullptr
        while ( fast && fast->next) {
            slow = slow->next; // 一次走一步
            fast = fast->next->next; // 一次走兩步

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list 中的元素
  • space：$O(1)$ ➔ 只需要常數空間