既然能够判断出是否是有环路&＃xff0c;那改如何找到这个环路的入口呢&＃xff1f; 思路类似找单链表的交点。

解法如下&＃xff1a; 当p2按照每次2步&＃xff0c;p1每次一步的方式走&＃xff0c;发现p2和p1重合&＃xff0c;确定了单向链表有环路了

接下来&＃xff0c;让p2回到链表的头部&＃xff0c;重新走&＃xff0c;每次步长不是走2了&＃xff0c;而是走1&＃xff0c;那么当p1和p2再次相遇的时候&＃xff0c;就是环路的入口了。

这点可以证明的&＃xff1a;

在p2和p1第一次相遇的时候&＃xff0c;假定p1走了n步骤&＃xff0c;环路的入口是在p步的时候经过的&＃xff0c;那么有

p1走的路径&＃xff1a; p&＃43;c &＃xff1d; n&＃xff1b;         c为p1和p2相交点&＃xff0c;距离环路入口的距离

p2走的路径&＃xff1a; p&＃43;c&＃43;k*L &＃61; 2*n&＃xff1b;   L为环路的周长&＃xff0c;k是整数

显然&＃xff0c;如果从p&＃43;c点开始&＃xff0c;p1再走n步骤的话&＃xff0c;还可以回到p&＃43;c这个点

同时p2从头开始走的话&＃xff0c;经过n步&＃xff0c;也会达到p&＃43;c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同&＃xff0c;所以当p1和p2再次重合的时候&＃xff0c;必然是在链表的环路入口点上。