快慢指针法
算法步骤
- 初始化快慢指针
- 循环处理，快指针走两步，慢指针走一步，直到发现环或者到达链表结尾
伪代码
// 1. 节点数为1和2的情况
if head == head.next
return true
slow = head
fast = head.next != null ? head.next.next : null
if slow == fast
return true
// 2. 循环
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
环起点的问题
快慢指针法可以简化为“追击问题”，即在慢指针进入环的那一刻，快指针开始追击慢指针。如何求进入环的点？
image.png
解：
相遇时有公式
将(1)、(2)代入(3)有，
进而有，
可知道相遇时，相遇点与起点的距离为环的整数倍。
所以，可以通过将指针分别置于起点和相遇点，以步长为1遍历，两个指针必然会在环起点相遇。
p1 = meetPoint
p2 = head
while p1 != p2
p1 = p1.next
p2 = p2.next
return p1
