这不是使用著名的龟兔法在链表中检测循环的问题。
In the Hare &乌龟方法，我们有指针以1x和2x的速度运行，以确定它们相遇，我相信这是最有效的方法，这种搜索的顺序是O(n)。
问题是我必须提出一个证明(证明或反驳)，当移动速度为Ax (a乘以x)和Bx (B乘以x)并且a不等于B时，两个指针可能总是相遇。其中a和B是两个随机整数，在链表上操作，存在一个循环。
这是我最近参加的一个面试中问到的问题，我无法全面地向自己证明上述情况是否可能。
假设存在一个长度为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)
为k取n = k*L-m, k*L>m足够大，但可能有一个更小的解决方案。
因此，是的，他们总是见面。
如果你的两个步长有一个共同的因子x:假设步长是Ax和Bx，那么只考虑你从原始序列和每个x元素中得到的序列。这个新序列有一个循环当且仅当原序列有一个循环，并且在其上取大小为a和B的步长相当于在原序列上取大小为Ax和Bx的步长。
这个约简意味着足以证明当A和B是素数时算法有效
假设是错误的。例如，如果两个指针的跳跃大小都为偶数，则循环大小也为偶数，指针之间的距离为奇数，则它们永远不会相遇。
这显然是一个不可能的情况。因为两个指针从同一点开始，所以它们之间的距离总是相等的。