1

现在我记得阅读堆栈溢出答案时,快跑者和慢跑者总是会在链表循环中发生冲突,并且速度差 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

这个例子和循环中的跑步者总是会发生碰撞的说法是矛盾的,因为快跑者可以不断跳过慢跑者。

我还没有上过算法课程,所以请尽量简单地解释我做错了什么。

4

0 回答 0