快慢指针求环入口问题：_快慢指针判断环入口

1. 是否存在环：

在寻找环入口之前，我们需要先判断是否存在环。判断的方式有很多，经典的方法就是快慢指针。所谓快慢指针，就是用两个指针，一个每次只移动一步，一个每次移动两步，移动块的指针我们称之为快指针，类似“斥候”，用于探路。如果快指针到达了空节点，那么说明不存在环，如果快慢指针相遇，则必定存在环。

2. 环入口：

先说结论，当快慢指针相遇后，我们将快指针重置回head头节点（或者重新设立一个位于head的指针），与慢指针同速率移动，二者相遇的地方就是环入口。

证明：

将链表分段，从开头到环入口的距离为L，快慢指针在第t次移动后相遇的位置为X（从环入口开始数），从X位置继续前进，到达环入口的距离记为Y，则有下面的关系：

(1) 快指针走过的距离为2*t = L+n*(X+Y)+X, n为双指针相遇前快指针在环内循环的圈数
(2) 慢指针走过的距离为t = L+X

联立式子1和式子2，得到：0 = -L+n*(X+Y)-X => L = n*(X+Y)-X，且n必定是大于等于1的（快指针必然绕过1圈才能到达慢指针的后面，才有机会与慢指针相遇）

右边的式子，如果我们再减去一个Y，就会变成(n-1)*(X+Y),正好是完整的环长度，走过Y个距离，应该正好回到环入口，我们设环入口的位置为0，则有L-Y=0，得出L=Y，这意味着，快慢指针相遇的位置出发到达环入口的距离，就是从头节点出发到达环入口的距离。

因此，如果我们设一个指针从头节点走，而另一个指针从位置X开始走，二者走过L个距离，应该正好到达环入口。

3. 为什么快指针要移动2格，移动3格，4格不行吗？

当然可以更快，但是快指针不是越快越好。如果它移动的速度超过了环的长度Q，那么它每次都会走超过环长度的步数（假设为n），那走n步与走n%Q步是等价的，因为它绕了好几圈，回到了环入口，最终也只比它之前的位置多走了n%Q步。如果n%Q==1，那快指针实际上和慢指针的速度是一样的，一旦错过，就永远不会相遇了。之所以设置成2，是因为单向链表的环的长度最少为3，两个节点是无法形成环的。