142. Linked List Cycle II

題目
思路：最直覺的作法就是從頭開始沿著 next 一直走，然後用一個 set 來存放走過的 node，如果再次走到已走過的 node 就是 cycle 起點

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return curr
        memo.add(curr)
        curr = curr.next
    return

• 平均時間複雜度：O(n)
  • 因為 in 和 add 對於 set 來說都是 O(1)，所以 while 迴圈內每次執行的複雜度為 O(1)
• 平均空間複雜度：O(n)

如果想讓空間複雜度是 O(1) 呢？

此時必須使用 Floyd’s Cycle Detection algorithm，但假如之前沒看過這個演算法，怎樣的思路最有可能導向用它來解呢？此演算法背後的原理又為何？

1. Linked list 不要動用額外空間最直覺的解題方式，就是單純靠指標的移動來解，而這題顯然無法靠單一指標做到。那雙指標做得到嗎？

2. 假如用快慢雙指標同時從起點出發的話，他們會在 cycle 裡交會，而我們要知道 cycle 起點的唯一方法，就是想辦法讓兩個指標在 cycle 起點交會，如何做到？

   • 快指標走的速度是慢指標的兩倍

3. 想讓指標在 cycle 起點交會，首先必須知道各段距離之間的關聯，我們可以畫個圖，把 起點、cycle 起點、cycle 裡的交會點 先標示出來，利用我們目前已知的條件：在 cycle 裡交會時，快指標走的距離是慢指標的兩倍 來列出方程式，釐清各個距離之間的關係。下面這個影片從 6:37 開始把推導過程講得很清楚

   • 不過影片講解的最後有個地方我覺得可以再多講一下，影片裡一開始假設快指標比慢指標多走了一圈 cycle，最後放寬這個限制，因為快指標有可能多走超過一圈 cycle，此時等式覺得這樣改寫比較容易懂：

     1 2 3

     2 * slow = fast 2 * (p + c - x) = p + 2c - x + nc # n 可為 0 或正整數，代表快指標除了已經多走了一圈之外，又再多走的圈數 p = x + nc

     • 最後的 p = x + nc 代表：就算走完 x 還無法會合，只要再多走 n 圈還是會相會，而且一定還是會在 cycle 起始點會合

4. 如影片裡所說，當快慢指標會合後，把其中一個指標放回原點，再讓兩個指標同速往前，他們的交會點就會是 cycle 起點

5. 雖然講完之後感覺程式寫起來蠻簡單，但我一開始還是犯了個小錯誤，一開始寫法如下：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: fast = slow = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # slow 與 fast 交會 break else: return node = head while slow: slow = slow.next node = node.next if slow is node: return node

   有發現錯在哪嗎？當 case 是這張圖 的時候，我回傳的 node 是 val 為 2 的 node 而非正確答案。問題出在我沒有考慮到一個情境：當快慢指標會合之後，那個點有可能已經是 cycle 起點了，而當這個起點又剛好是 head 的時候，上面的程式就會出錯

   • 我錯在假設在 fast & slow 第一次相會之後，slow & node 兩個指標一定要動才會相會，但當 cycle 起點也是 head 的時候，他們不一定要動就可能相會。所以要改的部分就是第 16 行之後，因為它們一定會相遇，while 條件可以改成 while node is not slow:，只要他們還沒相遇就做移動，直到相遇為止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    fast = slow = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # slow 與 fast 交會
            break
    else:  # fast 走到底了兩個都還沒交會
        return
    node = head
    while node is not slow:
        slow = slow.next
        node = node.next
    return node

這邊稍微提一下 Python 的 while-else，它是別的語言比較沒有的用法，但有時候還蠻好用的。else 的內容會在 while 正常結束時被執行，也就是當 while 被 break 之後，是不會執行 else 內容的。所以這邊的用法就是：

• 當 slow 與 fast 交會，就繼續往下做
• 當 fast 走到底了兩個都還沒交會，就是沒有 cycle，此時直接 return

如果不用 while-else，就必須在 while 後面寫

1
2

if not fast or not fast.next:
    return

相對來說比較沒那麼簡潔