algorithm - 循环检测算法 : Is there a condition for Tortoise and Hare to enter into cycle?

Question

最近参加一个面试，遇到了下面这个问题，一直想不通。

问题一:

根据我读到的证明，乌龟一次移动 1 步，而兔子一次移动 2 步。我明白这一点，他们会在某个时候相遇，因为兔子的移动速度是乌龟的两倍。他们不能有任何随机值，例如 2 和 3 或 3 和 5 或 2 和 4。如果是这样，他们会找出循环吗？选择龟兔赛跑值的条件是什么？我们可以选择任何随机值吗？

问题2:

龟兔赛跑是否有进入循环的条件？假设 Tortoise 和 Hare 是否具有以下值分别为 2 和 4。链表就像

            3   
          /   \
    1 -  2     4
          \   /
            5

如果乌龟在节点 3 进入循环，而兔子在节点 2 进入循环，那么它们都不会在循环内相遇。那么龟兔赛跑是否有进入循环的条件呢？

是否应该选择任何受限的值以使它们彼此相遇？

Answer 1

RE Q1:龟兔赛跑速度的最大公约数不能是循环长度的除数(1 除外)。所以例如如果 gcd(vTortoise, vHare)=2，它将检测奇数长度的循环，但对于偶数长度的循环可能会失败。 Q2涉及失败的情况。

RE Q2: 当上述限制不成立时检测循环，即当循环长度被M = gcd(vTortoise, vHare) 整除时，如果 tortoise 和兔子从循环开始处以不同模 M 的位置进入循环。所以在上面的例子中，M=2 如果兔子和乌龟都进入模数 M 相等的位置，则将检测到循环，例如0和2，0和4，2和4，1和3，等等。但是如果他们进入循环，则不会检测到循环(因此龟兔会无限旅行)例如在位置 0 和 1，或 0 和 3，1 和 2 等。