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

Question

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

Answer 1

在现实生活中，您可能永远不需要检测链表中的循环，但这样做的算法很重要，我已经在现实生活中多次使用它们。

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

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

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

预计到达时间:

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