快慢指針法
算法步驟
- 初始化快慢指針
- 循環(huán)處理觅玻，快指針走兩步，慢指針走一步，直到發(fā)現(xiàn)環(huán)或者到達鏈表結(jié)尾
偽代碼
// 1. 節(jié)點數(shù)為1和2的情況
if head == head.next
return true
slow = head
fast = head.next != null ? head.next.next : null
if slow == fast
return true
// 2. 循環(huán)
for fast ≠ null and slow ≠ fast
if fast.next ≠ null
fast = fast.next.next
else
return false
slow = slow.next
return fast ≠ null and fast == slow
環(huán)起點的問題
快慢指針法可以簡化為“追擊問題”，即在慢指針進入環(huán)的那一刻，快指針開始追擊慢指針思灌。如何求進入環(huán)的點？
image.png
解：
相遇時有公式
將(1)晨继、(2)代入(3)有檀葛，
進而有，
可知道相遇時，相遇點與起點的距離為環(huán)的整數(shù)倍影涉。
所以孵户，可以通過將指針分別置于起點和相遇點何址，以步長為1遍歷偎血，兩個指針必然會在環(huán)起點相遇。
p1 = meetPoint
p2 = head
while p1 != p2
p1 = p1.next
p2 = p2.next
return p1
