该算法使用快速和慢速指针来检测链表中的循环。我的问题是，如何证明循环中两个指针碰撞的点到循环开始的距离等于链表头部到循环开始的距离？
问问题
713 次
1 回答
-1
将慢速指针的速度视为“x”，将快速指针的速度视为“2x”。使用简单的相对运动，您可以证明如果存在循环，这两者最终会相遇。
现在，考虑时间相同，所以快指针行进的距离是慢指针的两倍。
如果慢速行进 a+b 的距离，那么快速行进 a+2b+c。该链接将使您更好地理解。
2*(a+b)=a+2b+c
求解这个方程可以得到 a=c。
这个问题已经回答过了，你可以参考下面的链接：
https ://cs.stackexchange.com/questions/10360/floyds-cycle-detection-algorithm-determining-the-starting-point-of-cycle
于 2020-07-04T14:50:15.080 回答