題目出處

141. Linked List Cycle

難度

easy

題目分類

Hash Table, Linked List, Two Pointers

個人範例程式碼

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。

Reference

• AC Python 76ms Floyd loop detection in 7 lines
• Except-ionally fast Python