现在我记得阅读堆栈溢出答案时,快跑者和慢跑者总是会在链表循环中发生冲突,并且速度差 2 是任意的。
如果快跑者和慢跑者之间的差异是 2,那么我无法想出一个反例,但是如果跑者之间的差异是 3,那么我似乎无法在下面的示例中让跑者发生碰撞.
假设我们在一个链表循环中有 2 个跑步者,慢的和快的。循环有 8 个节点,第一个节点标记为 0,第二个节点标记为 1,依此类推。慢在索引 0 处,快在 1 处,那么它们永远不会发生碰撞:
slow fast
0 1
1 4
2 7
3 2
4 5
5 0
6 3
7 6
0 1 # pattern seems to restart here
这个例子和循环中的跑步者总是会发生碰撞的说法是矛盾的,因为快跑者可以不断跳过慢跑者。
我还没有上过算法课程,所以请尽量简单地解释我做错了什么。