個人範例程式碼 - 二刷 (2026/08/05)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True

        return False

算法說明

經典的龜兔賽跑演算法，如果有環，一次跑兩步的最終會與跑一步的重疊。

註：這裡使用 is 而非 == 語義會更清楚，因為 == 可以透過 eq 定義如何相等，但 is 指的是記憶體上面的相等，必定指同一個 node。

Time Complexity

O(n)

Space Complexity

O(1)

Boundary conditions

留意 no cycle 的邊界處理

1. []
2. [0]
3. [0, 0]

個人範例程式碼 - 一刷 (2022/03/05)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head 
        # while slow.next and fast.next.next:  # check exist
        # while fast.next and fast.next.next:  # check exist
        while fast and fast.next:  # check exist
            slow = slow.next
            fast = fast.next.next
            if slow is fast: # has cycle
                return True
        return False # no cycle

Time Complexity

x

Space Complexity

x

算法說明

這題考 Linked List 的遍歷操作，
最麻煩的應該是邊界控制，這我們下面再提。

Floyd Cycle Detection Algorithm, Tortoise and Hare Algorithm (龜兔賽跑演算法)

演算法使用的是「Floyd Cycle Detection Algorithm, Tortoise and Hare Algorithm (龜兔賽跑演算法)」

或簡稱 Floyd Cycle 之類的，簡單來說就是當一個東西有環，
我們放一個跑比較快(step2)的兔子跟跑比較慢(step1)的烏龜，
兔子跟烏龜在有環的情況下，它們遲早會相會。

corner case 特殊情況處理

要處理沒有東西 [] 的情況… 被搞到

Boundary conditions/ Edge conditions 邊際情況處理

這題我犯了兩次錯誤，

第一次我寫 while slow.next and fast.next.next:

會跳錯，因為 slow 並不重要，fast 跑在前都會先檢查過了，
當會跳錯的地方在於「fast.next」不存在。

第二次我寫 while fast.next and fast.next.next:

還是錯，原因是這樣沒有處理到當 「fast」 不存在的情況。

第三次 while fast and fast.next 就是正確的了，

我們可以保證 fast 與 fast.next 必存在，
而 fast.next 可以指向 None，
當 fast = fast.next.next 時，我們會在下一個迴圈把 None 判出來。

補充 - 系統思維加速 (面試題)

也可以用 hashset() 的方式來實作，hash pointer。