# 快慢指針
###### tags: `LeetCode筆記` `鏈結串列`

>可以用在找linked lsit 的middle 因為，當快指針到了end ，慢指針會剛好到中間，因為兩個速度差一倍。

例題] 環形鏈表（Linked-List Cycle）
問題
給定一個單向鏈結串列（Singly Linked-list）的頭部節點，撰寫一支函數判斷這個鏈結串列是否存在迴圈（cycle）。

題解
想像有兩位跑者在圓形操場上奔跑，如果其中一位跑者的速度比另外一位跑者要來的快，那麼勢必會趕上並從後面越過較慢的跑者。這樣的思路可以用來設計一種演算法，來確定鏈結串列是否存在迴圈。

分別採用慢速指針 slow 和快速指針 fast 遍歷鏈結串列，每次執行時讓慢速指標移動一步，快速指標移動兩步。可以得到以下事實：

如果鏈結串列沒有迴圈，則 fast 會先抵達鏈結串列的末端
如果鏈結串列沒有迴圈，則 slow 永遠不會與 fast 相遇
如果鏈結串列存在迴圈，則 fast 和 slow 先後進入該迴圈。並且在此之後，兩個指針會在迴圈中無限移動。如果在一階段兩個指針相遇了，就可以得到「鏈結串列存在迴圈」的結論。

接下來讓我們分析一下這兩個指針是否有可能相遇。當 fast 從後面接近 slow 時，有兩種可能性：

fast 比 slow 慢一步
fast 比 slow 慢兩步
快指標和慢速指標之間的所有其他距離將減少到這兩種可能性之一。讓我們分析一下這些場景，考慮到快速指標總是先移動：

如果 fast 比 slow 慢一步：fast 移動兩步，slow 移動一步，彼此相遇
如果 fast 比 slow 慢兩步：fast 移動兩步，slow 移動一步，等同上一場景，意味兩個指針將在下一次反覆運算中相遇
由上述分析可知：如果鏈接串列中存在迴圈，則兩個指針必定會相遇。上述討論的直觀表示如圖所示：


## code

def has_cycle(head):
    slow, fast = head, head
    
    while fast and fast.next: 
        fast = fast.next.next
        slow = slow.next
        
        if slow == fast:
            return True
    
    return False

另一種寫法

while(fast !== slow) {
  if(fast === null || fast.next === null) {
    return false;
  }
    
  fast = fast.next.next;
  slow = slow.next;
}
  
return true;

## 自己心得
邊界值是這個的原因而不是fast.next.next原因是
如果fast.next 存在的話，fast.next.next 如果是none 也沒差。
所以只要不要讓fast.next =none 成立，因為如果成立
fast.next.next 就錯了，因為none.next 是殺小
`while fast and fast.next: `