algorithm - 为什么我们需要检测链表中的循环

Question

我看到很多关于如何检测链表中的循环的 Q/A，但我想了解我们为什么要这样做，换句话说，检测链表中的循环的实际用例是什么

标签： algorithmdata-structureslinked-listcyclic-reference

Answer 1

在现实生活中，您可能永远不需要检测链表中的循环，但是执行此操作的算法很重要，我在现实生活中多次使用它们。

例如，我经常会递归地处理一个应该是树形的链接数据结构。但是，如果它不是树形并且有一个循环，那将导致无限递归和堆栈溢出，所以我喜欢在它爆炸之前抓住它。我通常为此使用 Brent 的循环查找算法，因为它很容易适应我的递归处理并且开销极低。

循环查找算法在 Pollard 的“rho”分解算法中也很有用（https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm）

你在学习这些算法时学到的想法在以后学习其他更复杂的东西时也会很有用。

预计到达时间：

我应该补充一点，错误产生循环的常见情况是用户专门创建链接的情况。例如，在 Java 中，一个类可以有一个超类，class C extends A {}例如，程序员编写 . extends关键字创建类之间的链接。如果他也写class A extends C了 ，那么他已经创建了一个循环，编译器必须检测那个条件。