快慢指针法

算法步骤

1. 初始化快慢指针
2. 循环处理，快指针走两步，慢指针走一步，直到发现环或者到达链表结尾

伪代码

// 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