algorithm - 链表中的循环检测 : Exhaustive theory

Question

这不是关于使用 famous 在链表中检测循环的问题龟兔赛跑法。

在 Hare & Tortoise 方法中，我们有指针以 1x 和 2x 的速度运行以确定它们是否相遇，我相信这是最有效的方法，这种搜索的顺序是 O(n)。

问题是我必须提出一个证明(证明或反驳)当移动速度为 Ax(A 乘以 x)和 Bx(B 乘以 x)且 A 为不等于 B。其中 A 和 B 是在存在循环的链表上运行的两个随机整数。

这是在我最近参加的一次采访中被问到的，我无法向自己全面证明上述是否可能。任何帮助表示赞赏。

Answer 1

假设有一个循环，长度为L .

简单情况优先

为了简单起见，首先考虑两个粒子同时整个循环的情况。每当 n*A = n*B (mod L) 时，这些粒子都处于同一位置对于一些正整数 n ，这是他们再次相遇之前的步数。以n=L给出一个解决方案(尽管可能有一个更小的解决方案)。所以在L之后时间单位，粒子 A做了A绕着循环回到起点和粒子 B做了B绕着环路旅行回到起点，他们在那里快乐地碰撞。

一般情况

现在当它们不同时进入循环时会发生什么？让A是较慢的粒子，即 A<B ，并假设 A在时间 m 进入循环, 让我们称这个位置为 A进入循环 0 (因为他们在循环中，他们永远不能离开它，所以我只是通过减去 A*m 重命名位置，距离 A 在 m 时间单位之后移动)。然后，那个时候，B已经在位置 m*(B-A) (它在 m 时间单位之后的实际位置是 B*m，因此它的重命名位置是 B*m-A*m )。然后我们需要证明有一个时间n这样 n*A = n*B+m*(B-A) (mod L) .也就是说，我们需要模方程的解

(n+m) * (A-B) = 0 (mod L)

服用 n = k*L-m对于 k足够大 k*L>m可以解决问题，但同样可能有更小的解决方案。

因此，是的，他们总是会见面。