Fast & Slow Pointers快慢指標
找中點、環偵測（Floyd）、環的起點。
用在：偵測循環參照、找中點切半
01為什麼需要它
物件 A 指向 B、B 指向 C、C 又指回 A。要偵測這種環，最直覺的方法是把走過的節點記在 set 裡，但那要 O(n) 的額外記憶體。
為什麼用它一快一慢兩個指標在同一條路上跑：沒有環，快的先到終點；有環，快的在環裡繞，遲早從後面追上慢的。O(1) 空間。這是 Floyd 判圈演算法。
要把串列切成兩半（合併排序、判斷回文），得知道中點在哪。但串列沒有長度欄位，數一次長度再走一半要掃兩遍。
為什麼用它fast 每次走兩步、slow 走一步，fast 到底的時候 slow 剛好走了一半。一遍搞定，而且程式碼只有四行。
函數 f 反覆套用 x → f(x) → f(f(x))，狀態有限所以終究會進入循環。要找出循環從哪開始、長度多少，不能把所有狀態存下來。
為什麼用它把「x 的下一個是 f(x)」看成串列，這就是找環起點。Pollard 的 rho 因數分解也用同一個技巧。
看到這些關鍵字就想到它：有沒有環、環的起點、中點、倒數第 k 個、只能走一遍、不能用額外空間、兩個指標速度不同。
02核心概念
快慢指標是讓兩個指標以不同速度或不同起點在同一條串列上前進，利用它們之間的距離關係回答問題。慢指標一次一步，快指標一次兩步：fast 走的距離永遠是 slow 的兩倍，所以 fast 到終點時 slow 在中點。
偵測環用的是追逐的直覺。若有環，fast 進環後會一直繞；slow 進環後，fast 每一輪追近 1 步，最多繞一圈就追上。若沒有環，fast 會先碰到 None。整個過程只用兩個指標，O(n) 時間、O(1) 空間。
找環的起點多一個階段。設 head 到環起點距離 a、環長 c。相遇時 slow 走了 a + b，fast 走了 2(a + b)，兩者差是環長的整數倍，推得 a ≡ −b (mod c)。意思是：從相遇點再走 a 步，剛好回到環起點。所以把一個指標放回 head、另一個留在相遇點，兩個都一次一步，再相遇的地方就是起點。
同一家族還有固定間距的用法：fast 先走 k 步，再和 slow 同速前進，fast 到底時 slow 在倒數第 k 個。關鍵都是「兩個指標之間維持一個已知的關係」。
03演算法步驟
- 1
slow = fast = head。迴圈條件永遠是while fast and fast.next，這樣fast.next.next才不會炸。 - 2每一輪
slow = slow.next、fast = fast.next.next。 - 3找中點：迴圈結束回傳 slow。偶數長度會停在第二個中點；要第一個就把 fast 從
head.next出發。 - 4偵測環：每一輪移動後檢查
slow is fast。注意是移動後才比，一開始兩者本來就相同。 - 5環的起點：相遇後
slow = head，兩個指標都一次一步直到再相遇。倒數第 k 個：fast 先走 k 步再同速前進。
04互動示範
「找中點」看 fast 到底時 slow 停在哪；「偵測環」看兩個指標怎麼在環裡相遇，以及第二階段怎麼找出環的起點。
05程式碼
四個函式共用同一個骨架：中點、判圈、環起點、倒數第 k 個。注意迴圈條件都一樣，差別只在什麼時候停、停下來後做什麼。
# 找中點：fast 走兩步、slow 走一步，fast 到底時 slow 在中間
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # 偶數長度時回傳第二個中點
# 偵測環（Floyd）：有環的話 fast 一定會追上 slow
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# 找環的起點：相遇後把一個指標放回 head，兩個都走一步，再相遇處就是起點
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
# 倒數第 k 個：fast 先走 k 步，再一起走，fast 到底時 slow 在倒數第 k 個
def kth_from_end(head, k):
slow = fast = head
for _ in range(k):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
return slow06練習題
- LeetCode 876Middle of the Linked ListEasy
- LeetCode 141Linked List CycleEasy
- LeetCode 142Linked List Cycle II（環的起點）Medium
- LeetCode 19Remove Nth Node From End of List（固定間距）Medium
- LeetCode 287Find the Duplicate Number（把陣列當串列找環）Medium
- LeetCode 143Reorder List（中點 + 反轉 + 交錯合併）Medium