确定链表中是否有循环的最佳(停止)算法是什么？

[Edit]对时间和空间的渐进复杂性进行分析将很不错，因此可以更好地比较答案。

[编辑]最初的问题不是要解决outdegree> 1的节点，但是有一些讨论。这个问题更像是"在有向图中检测循环的最佳算法"。

解决方案

回答

使用哈希表存储已经看到的节点(从列表开始按顺序查看它们)怎么样？实际上，我们可以实现接近O(N)的目标。

否则，使用排序堆而不是哈希表将实现O(N log(N))。

回答

有两个指针遍历列表。使一个迭代速度是另一个迭代速度的两倍，并比较每个步骤的位置。在我的头顶上，像这样：

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n)，尽你所能。

回答

我想知道是否还有其他方法，而不是在前进时迭代填充数组并检查数组中是否已存在当前节点...

回答

如果周期未指向起点，则康拉德·鲁道夫(Konrad Rudolph)的算法将无法正常工作。以下列表将使它成为一个无限循环：1-> 2-> 3-> 2.

DrPizza的算法绝对是必经之路。

回答

In this case OysterD's code will be the fastest solution (vertex coloring)

那真的会让我感到惊讶。我的解决方案最多使列表通过两次(如果最后一个节点链接到倒数第二个极点)，而在通常情况下(无循环)将仅通过一次。没有哈希，没有内存分配等。

回答

In this case OysterD's code will be the fastest solution (vertex coloring)

那真的会让我感到惊讶。我的解决方案最多使列表通过两次(如果最后一个节点链接到倒数第二个极点)，而在通常情况下(无循环)将仅通过一次。没有哈希，没有内存分配等。

是的。我注意到这种表述并不完美，因此改写了它。我仍然相信，聪明的散列操作可能比头发快一些。我相信算法是最好的解决方案。

只是为了强调我的观点：Vertec着色被现代垃圾收集器用来检测依赖项中的循环，因此有一个非常真实的用例。他们大多使用位标志来执行着色。

回答

我们将必须访问每个节点来确定这一点。这可以递归完成。为了阻止我们访问已访问的节点，我们需要一个标记来表示"已访问"。当然，这不会给我们循环。因此，请使用数字代替位标志。从1开始。检查连接的节点，然后将其标记为2，然后递归直到网络覆盖。如果在检查节点时遇到的节点比当前节点小一个以上，则我们有一个循环。周期长度由差值给出。