快慢指针法判断环入口位置 LeetCode142 环形链表2_快慢指针为什么能找到正确的入口位置

快慢指针如何寻找环入口

通过快慢指针思路来判断链表是否有环时，我们可以通过判断两个指针最终是否会相遇来确定。但是问题在于，这样得到的相遇点并不是环的入口，想要通过快慢指针来寻找环入口还需要做一些额外的处理。

思路：参考LeetCode142题，在第一次相遇后，重新设置一个指向head的指针，然后重新让新指针与慢指针开始行动，每次移动距离都为1，这样一来下次相遇的点就是环入口了。代码实现见底部

具体解释为什么两个指针再次相遇的地方就是环入口：

1. 将存在环的链表长度理解为a+b；a为非环的链表部分，b为环的长度
2. 设快指针走过的距离为f，慢指针走过的距离为s
3. 在第一次相遇时，因为快指针每次走2步，慢指针每次走1步，所以f=2s。而快指针能追上慢指针，肯定是比慢指针多跑了n次b环才相遇的，n为整数，值为多少不重要（可以设想一下现实中跑步的场景）。所以快指针走过的路径也可以表示为f=s+nb，也就是链表的非环部分加上跑过的环的次数。
4. 根据f=2s和f=s+nb这两个公式，可以得到慢指针走过的距离可以表示为s = nb。
5. 而对于一个遍历链表的指针来说，它停留在入口时走过的步数一定是 a+nb。因为a就是环的入口，后续每把环（b