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

Question

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

[编辑]对时间和空间的渐近复杂性的分析将是甜蜜的,因此可以更好地比较答案.

[编辑]原始问题没有解决超过1的节点,但有一些关于它的讨论.这个问题更像是"在有向图中检测周期的最佳算法".

Answer 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),这是你能得到的最好的.