文章目錄
- 判斷是否有環
- 找到環的入口
環形連結清單，就像下面這樣的連結清單。
環形連結清單有兩種主流題目，一種是判斷該連結清單是否有環，另一種就是找到環形連結清單的環入口。
這兩種題要是沒有一定的方法，判斷起來會非常亂，是以總結一下方法。
判斷是否有環
使用快慢指針法，分别定義 fast 和 slow 指針，從頭結點出發，fast指針每次移動兩個節點，slow指針每次移動一個節點，如果 fast 和 slow指針在途中相遇 ，說明這個連結清單有環。
為什麼快慢指針一定會在環内相遇呢？
我一開始也是這個問題，為什麼他們不會錯開呢，其實這個問題畫一個連結清單走一下就知道了，fast指針一次走兩個，slow一次走一個，也就是他們兩個相對的位移是一個機關，即fast指針每次以一個機關的距離靠近slow，是以不會錯開。
對應題目： leetcode 141. 環形連結清單
完整代碼：
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 卡哥一刷
fast = head
slow = head
while fast!=None and fast.next !=None:
fast = fast.next.next
slow = slow.next
if fast == slow:
# 兩者在環内相遇了
return True # 有環
return False # 沒有環 找到環的入口
這種題的思路其實比較麻煩，要不是我看了卡哥的推導，估計會在這裡卡上一陣。
設一個環形連結清單如下圖所示。
先放結論：
從頭結點出發一個指針，從相遇節點 也出發一個指針，這兩個指針每次隻走一個節點， 那麼當這兩個指針相遇的時候就是 環形入口的節點。
證明過程我覺得沒幾個人想看，雖然很簡單，但是也懶得看，是以我放最後了。
對應題目：leetcode 142. 環形連結清單 II
完整代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 卡哥一刷
fast = head
slow = head
while fast!=None and fast.next !=None:
fast = fast.next.next
slow = slow.next
if fast == slow:
# 兩者在環内相遇了 記錄此時下标值
index1 = fast
index_start = head # 記錄開始點
while index1 != index_start:
# 兩者同時移動，在相交的時候就是環的入口
index1 = index1.next
index_start = index_start.next
return index1
return None 證明過程：
slow指針走過的節點數為: x + y， fast指針走過的節點數：x + y + n (y + z)，n為fast指針在環内走了n圈才遇到slow指針， （y+z）為 一圈内節點的個數A。
因為fast指針是一步走兩個節點，slow指針一步走一個節點， 是以 fast指針走過的節點數 = slow指針走過的節點數 * 2：
(x + y) * 2 = x + y + n (y + z)
兩邊消掉一個（x+y）: x + y = n (y + z)
因為要找環形的入口，那麼要求的是x，因為x表示 頭結點到 環形入口節點的的距離。
是以要求x ，将x單獨放在左面：x = n (y + z) - y ,
再從n(y+z)中提出一個 （y+z）來，整理公式之後為如下公式：x = (n - 1) (y + z) + z 注意這裡n一定是大于等于1的，因為 fast指針至少要多走一圈才能相遇slow指針。
拿n為1的情況來舉例，意味着fast指針在環形裡轉了一圈之後，就遇到了 slow指針了。
當 n為1的時候，公式就化解為 x = z。
那麼 n如果大于1是什麼情況呢，就是fast指針在環形轉n圈之後才遇到 slow指針。
其實這種情況和n為1的時候 效果是一樣的，一樣可以通過這個方法找到 環形的入口節點，隻不過，index1 指針在環裡 多轉了(n-1)圈，然後再遇到index2，相遇點依然是環形的入口節點。