鏈表中環的入口結點
問題描述
給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。注意，pos 僅僅是用於標識環的情況，並不會作為參數傳遞到函數中。
說明：不允許修改給定的鏈表。
分析問題
拿到這個問題，我們最直觀的想法就是在遍歷結點的過程中去標記一下這個結點是否已經被訪問過。如果被訪問過，就代表這個結點是鏈表中環的入口點，我們直接返回就好。如果沒有被訪問過，我們就標記一下，然後接著去遍歷下一個結點，直到遍歷完整個鏈表為止。下面我們來看一下程式碼的實現。
def EntryNodeOfLoop(self, pHead):
tags = set()
while pHead:
#表示已經被訪問過了，代表有環
if pHead in tags:
return pHead
tags.add(pHead)
pHead = pHead.next
return None
我們可以看到該演算法的時間複雜度和空間複雜度都是O(n)。
優化
我們這裡也可以採用快慢指針來求解，就和上一題的解法類似，我們來看一下。
我們可以使用兩個指針fast和slow。他們都從鏈表的頭部開始出發，slow每次都走一步，即slow=slow->next，而fast每次走兩步，即fast=fast->next->next。如果鏈表中有環，則fast和slow最終會在環中相遇。
我們假設鏈表中環外的長度為a，show指針進入環後又走了b的距離與fast相遇，此時fast指針已經繞著環走了n圈。所以快指針一共走了a+n(b+c)+b=a+(n+1)b+nc的距離，我們知道快指針每次走2步，而慢指針每次走一步，所以，我們可以得出快指針走的距離是慢指針的兩倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。這裡你會發現：從相遇點到入環的距離c，再加上n-1圈的環長，恰好等於從鏈表頭部到入環點的距離。
因此，當發現slow和fast相遇時，我們再額外使用一個指針ptr指向鏈表頭部，然後它和slow指針每次都向後移動一個位置。最終，他們會在入環點相遇。
Tips: 你也許會有疑問，為什麼慢指針在第一圈沒走完就會和快指針相遇呢？我們來看一下，首先，快指針會率先進入環內。然後，當慢指針到達環的入口時，快指針在環中的某個位置，我們假設此時快指針和慢指針的距離為x，若x=0，則表示在慢指針剛入環時就相遇了。我們假設環的長度為n，如果看成快指針去追趕慢指針，那麼快指針需要追趕的距離為n-x。因為快指針每次都比慢指針多走一步，所以一共需要n-x次就能追上慢指針，在快指針遇上慢指針時，慢指針一共走了n-x步，其中x>=0，所以慢指針走的路程小於等於n，即走不完一圈就會相遇。
下面，我們來看一下程式碼實現。
def detectCycle(head):
if not head:
return None
#快慢指針
slow = head
fast = head
while True:
if not fast or not fast.next:
return None
fast=fast.next.next
slow=slow.next
#相遇時，跳出循環
if fast == slow:
break
ptr = head
while ptr != slow:
ptr=ptr.next
slow=slow.next
return ptr
該演算法的時間複雜度是O(n)，空間複雜度是O(1)。
如果覺得不錯，歡迎大家掃碼關注。
