list - 检测链表中的循环

Question

我在相关部分看到了这个问题，经过一些讨论后，我发现最常见的解决方案是兔子和乌龟算法。但是我看到的另一个建议的解决方案（这是我会做的）是包含一个 Node 类的第三个实例变量，它将跟踪它访问过的节点，就像一个布尔变量。那么这被认为是一个有效的解决方案吗？

Answer 1

你的解决方案绝对是一个有效的解决方案，因为它可以完成工作。

然而，检测循环的问题通常是通过使用O(1)额外内存的额外约束来制定的。hare and tortoise 算法满足此约束，而您的算法不满足：它需要O(N)额外的内存来存储每个节点的布尔值。