142. Linked List Cycle II

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 1.4k

種類 : linked list
難度 : medium
題目 : 142. Linked List Cycle II

思維邏輯

graph LR
A[3] --> B[2] --> C[0] --> D[-4] --> B

  1. 判斷是否有迴圈
    慢指針一次往前一個node、快指針一次往前兩個node，最後終會相交(指向相同node)

  2. 如何找出迴圈入口
    設$x$: head -> entrance節點數量
    設$y$: entrance -> 快慢指針相交的節點數量
    設$z$: 快慢指針相交的節點 -> entrance節點數量

    當slow與fast相交時，
    slow經過的節點數量為$x+y$
    fast經過的節點數量為$x+y+n(y+z)$，$y+z$從相交點的一個循環，$n$為循環次數
    因fast節點為slow兩倍，可得
    $$2(x+y) = x+y+n(y+z)$$
    兩側消除$x+y$，可得
    $$x+y = n(y+z)$$
    將右側$n$提出$-1$，可得
    $$x+y = (n-1)(y+z)+y+z$$
    $$x = (n-1)(y+z)+z$$
    這裡$(n-1)$可以得知：相交時，fast最少已經跑過1次循環
    而當$n=1$(也就是fast跑完1次循環後)，可得
    $$x=z$$
    這意味著：此時head -> entrance與相交點->entrance距離相同(雖然是廢話但我想很久😂)
    白話一點就是，現在我們已經到相交點了，再設一個指針從head開始跑，下次和這個指針相遇的節點就是entrance🎉🎉

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
快、慢指針
"""
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 當slow, fast相遇時
            if slow == fast:
                # slow從head開始
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. 如何判斷是否有cycle
  2. 找出迴圈的入口，需數學推導

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
集合法
這方法最簡單也蠻無腦的，我認為這個比快、慢指針淺顯易懂
但似乎會犧牲一點空間

雖然有想過用list儲存，但leetcode似乎不允許
"""
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        
        while head:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        
        return None

時間複雜度: O(n)
空間複雜度: O(n)