1 題目描述

判斷一個 linked list 是否有 cycle，如果有就返回 True，沒有就返回 False。

特殊要求空間複雜度為 O(1)。

2 解法

2.1 我的解法

一開始我的想法很簡單，但是空間複雜度為 O(n)。就是把每個節點都放進一個 set 裡面，如果有重複的節點就返回 True，否則返回 False。但是這個不滿足要求空間複雜度為 O(1)。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        check_dict = {}
        while head:
            check_dict.__setitem__(head, head.val)
            head = head.next
            if check_dict.get(head):
                return True
        return False

2.2 龜兔演算法

這個方法很巧妙，因為只能適用空間複雜度為 O(1)。通常可以存固定數量的變數，一個變數肯定不夠，那如果兩個變數呢？但是兩個變數怎麼確認是否有 cycle 呢？這時候就要用到龜兔演算法了。

原理也很好理解，想像一下在一個圓形的跑道上，兩個人跑步，一個人跑的快一點，一個人跑的慢一點，如果有 cycle，那麼不管兩個人從哪個位置出發，跑的過程中兩人一定會相遇。所以這裡我們使用兩個指針，fast和slow，fast每次走兩步，slow每次走一步，如果有 cycle，那麼fast和slow一定會相遇。

class Solution:
    def hasCycle3(self, head: Optional[ListNode]) -> bool:
        # Floyd's Tortoise and Hare Algorithm
        slow, fast = head, head

        while fast and fast.next:  # while not null
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True  # there is a cycle

        return False  # There is no cycle