问题标签 [floyd-cycle-finding]

我知道龟兔赛跑结束了一个循环的存在，但是如何将乌龟移动到链表的开头，同时将兔子保持在会场，然后一次移动两个步骤使它们在起点相遇周期？

我试图在 .NET 中的 C++ 上找到这个算法，但找不到，我找到了这个：

但似乎不对，还是我错了？我怎样才能真正证明我的兔子最终会遇到乌龟？提前感谢任何解释它是如何工作的proof

已编辑

关于这个解决方案，我发现在常规算法中他们只使用一个快速迭代器，但在这里他们使用两个，为什么？

我已经看了一下关于在链表中查找循环的算法的问题。我读过Floyd 的寻环算法解决方案，在很多地方都提到我们必须采用两个指针。一个指针（slow/tortoise）增加 1，另一个指针（faster/hare）增加 2。当它们相等时，我们找到循环，如果更快的指针达到 null，则链表中没有循环。

现在我的问题是为什么我们将更快的指针增加 2。为什么不做别的？增加 2 是必要的，或者我们可以将其增加 X 以获得结果。如果我们将更快的指针增加 2，我们是否有必要找到一个循环，或者可能存在我们需要增加 3 或 5 或 x 的情况。

假设我有一个函数 f：

f(0..12)：

我想找到循环开始和循环长度，分别为 1 和 4。龟兔算法适用于迭代函数，但我没有迭代函数。是否有其他算法适用于非迭代函数，或者可以为此修改龟兔算法吗？

编辑：

使用 Jason S 的回答，我设法想出了这个，这似乎是有效的：

我知道为了检测链表中的循环，我可以使用 Hare and Tortoise 方法，该方法包含 2 个指针（慢指针和快指针）。但是，在阅读 wiki 和其他资源后，我不明白为什么保证两个指针会在 O(n) 时间复杂度内相遇。

我在网上阅读了一些关于如何找到链表中是否存在循环的面试问题，解决方案（弗洛伊德的循环查找算法）是有两个指针，一个比另一个快 2 倍，然后检查它们是否再次相遇。

我的问题是：为什么我不能只保持一个指针固定，每次只将另一个指针向前移动 1 步？

在检测链表中的循环的最佳方法中，我们执行以下操作：

1. 使用 Floyd 的循环查找算法并在链表中识别循环内的位置。
2. 计算链表中循环的大小
3. 将一个指针定位在列表的开头，另一个“k”（其中 k 是循环的大小）定位。
4. 在迭代中，它们在循环开始时相遇。

我想知道为什么会这样。这背后的一些理论逻辑？

在面试问题中，“实施一种检测循环存在的算法。”。例如，链表有一个循环，如：

使用弗洛伊德的循环检测，这个问题可以通过使用快慢指针来解决。所以我应该尝试比较

一种。链接的节点值，即

快慢是类型Link

或者

湾。他们是否指向相同的参考，即if (fast == slow)

谢谢。

根据弗洛伊德的循环查找算法，龟兔赛跑的点解释了链表中的循环性质。

为了找到循环中的起始节点，我们将 tortoise 指针初始化为链表的头部，并开始将 hare 和 tortoise 指针递增一个单位。它们相遇的点表示循环的起始节点。

请告诉我它在给定情况下是如何工作的。

链接列表如下：

今天我正在阅读 Floyd 的在链表中检测循环的算法。我只是想知道如果我们跳过多个节点（比如 2 个）以更快地进行循环检测会不会更好？

例如：

请注意，更改时会考虑副作用fastptr。