【演算法分析】如何理解快慢指標？判斷linked list中是否有環、找到環的起始節點位置。以Leetcode 141. ...
快慢指標簡述
快慢指標經常用於連結串列(linked list)中環(Cycle)相關的問題。
- 快指標(fast pointer)和慢指標(slow pointer)都從連結串列的head出發。
- slow pointer每次移動一格，而快指標每次移動兩格。
- 如果快慢指標能相遇，則證明連結串列中有環；否則沒有。
快慢指標的具體程式碼(C++, Python, Java版本)可以參考ofollow,noindex" target="_blank">這個連結 。
LeetCode中對應題目分別是：
- 141. Linked List Cycle 判斷linked list中是否有環
- 142. Linked List Cycle II 找到環的起始節點（entry node）位置。
問題詳解 —— 為什麼如果有環，則快慢指標必定會相遇？
我們假設以下變數：
\(L_1\) ：起始節點(head node)到環起始節點(entry node)的距離。
\(C\)
: 環的長度。
假設我們的慢指標移動了\(x\) 步，那麼快指標就移動了\(2x\) 步。
那麼必定有\[(x-L_1)\% C= (2x-L_1) \% C \] \[(2x-x)\% C = 0\] \[x\%C=0\]
以上三個式子步步可逆，由於\(C\) 是給定的fixed value，而\(x\) 每步都在上升，因此必定有一個\(x=wC(w\in {N})\) 使得他們相遇。並且有\(L_1 \le x\) 所以必有\(x=\) ⌈\(\frac{L_1}{C}\) ⌉\(C\) 為他們第一次相遇的地點。因此有\(x< L_1 + C\) where\(x=\) ⌈\(\frac{L_1}{C}\) ⌉\(C\)
這也就意味著他們相遇的地方一定是慢指標在環裡的第一圈。
問題詳解 —— 如何找到環的起始節點？
我們再增加一些變數:
\(L_2\) : 環起始節點(entry node)到快慢指標相遇節點的距離。
\(k\) : 慢指標和快指標相遇的時候，慢指標走了的距離。
注意到，因為快指標走了的距離總是慢指標走了的距離的兩倍，因此
\(2k\)
是慢指標和快指標相遇的時候，快指標走了的距離。
由慢指標可以得出\[L_1+L_2=k\] 由快指標可以得出，其中n是快指標已經走過的圈數\[L_1+nC+L_2 = 2k\] 結合上述兩個式子，我們可以得出\[nC=k\]
當慢指標在遇到了快指標之後，慢指標又馬上移動了，那麼慢指標需要移動\(p\) 步後就可以讓慢指標就回到了環起始節點(entry node)。與此同時，在快慢指標相遇之後，又有一個指標馬上從原點出發，那麼它需要經過\(q\) 步才能到達起始節點(entry node)而且與慢指標相遇。
當慢指標和這個新指標相遇的時候，有\[(p-L_1)\%C=(q+L_2)\%C\]
由離散數學中的定理 可知\[(p-q-L_1-L_2)\%C=0\] \[(p-q-nC)\%C=(p-q)\%C=0\]
不妨取\(p=q\) 即\(p-q=0\Rightarrow （p-q）\%C=0\)
因此當他們同時回到環起始節點(entry node)的時候，有慢指標第一次相遇後走過的距離\(p\) 和新指標走的距離\(p=q\) 。
值得注意的是\(L_2< C\)，因此，他們第一相遇的時候必有
\(q<C-L_2\)
，也就是說慢指標和新指標第一次相遇的時候，他們必定都在環起始節點(entry node)。
LeetCode 對應程式碼
判斷linked list中是否有環(141. Linked List Cycle)
這個演算法的時間複雜度是O(n)
# Definition for singly-linked list. # class ListNode(object): #def __init__(self, x): #self.val = x #self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head is None: return False slow = head fast = head while(fast.next and fast.next.next): slow = slow.next fast = fast.next.next if slow == fast: return True return False
找到環的起始節點(entry node)位置(142. Linked List Cycle II)
# Definition for singly-linked list. # class ListNode(object): #def __init__(self, x): #self.val = x #self.next = None class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ if head is None: return None slow, fast, new_node = head, head, head while(fast.next and fast.next.next): slow = slow.next fast = fast.next.next if slow == fast: while slow != new_node: new_node = new_node.next slow = slow.next return new_node return None