我收到一个关于弗洛伊德循环寻找算法的面试问题：
弗洛伊德的寻环算法何时会失败？
我的意思是，是否有规则可以找到快速指针和慢速指针之间的步长？
问问题
1139 次
3 回答
2
在合理的假设下，它不会失败。它要么找到一个循环，要么断定没有循环。
我能想到的唯一失败场景如下：
- 实现中存在错误；
- 正在遍历的结构在算法进行时被修改。
于 2013-04-06T05:46:20.400 回答
1
Floyd 的循环查找算法可能不存在任何可能的故障情况。
唯一可能的失败场景发生在计算上难以在动态变化的链表中找到下一个节点时。
于 2013-04-06T05:55:14.040 回答
0
好的，我现在正在解决这个问题，我也遇到了同样的问题。
Floyd 算法指出，快指针可以比慢指针快 m 倍。人们通常将 m 视为 2，即在每次迭代中快速前进 2 步，而慢速前进仅 1 步。此特定值适用于所有结构和循环长度。
但是，如果我们要找到循环的开始并且我们取 m>2，那么在存在长度为 m-1 的循环的情况下算法会失败。在这种情况下，将检测到循环，但在查找初始循环节点方面失败。
这是我注意到的，但不确定如何以及为什么会这样。一些见解会有所帮助。谢谢！
于 2021-12-19T13:28:13.243 回答