algorithm - 测试链表是否具有循环的最佳算法

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

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

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

最佳答案

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

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)，尽你所能。