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

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

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

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

1> DrPizza..：

---

有两个指针在列表中迭代; 让一个以另一个的速度迭代,并比较它们在每一步的位置.在我的头顶,像:

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

---

顺便说一下,"脱离你的头脑"可能意味着你发明了这种算法的人,误导人们将其称为"DrPizza的算法"(!).让我们在到期时给予信任.早在1967年就由弗洛伊德出版:http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

---

@Herms,hare在循环体内设置为hare-> next,因此此时野兔可能为空.

---

哎呀,你确实有一个bug.while循环应该是`while(hare && hare = hare-> next),否则你可以直接迭代.

---

你不需要while(hare && hare = hare-> next).唯一能保护您的时间是列表为空(root为null).否则,只要hare-> next返回null,定义的while循环就会终止.

---

Stepanov&McJones在"编程元素"中对这个主题进行了非常详细的处理.第2章,您可以在这里阅读,http://www.elementsofprogramming.com/book.html涵盖了这一点.

---

我的意思是"脱离我的头脑",意思是"直接写入文本框而不参考编译器或其他任何东西".但是,你错了; Floyd的算法定位循环.这里的问题只是为了确定存在一个循环.两种算法背后的原理是相同的,但这实际上更简单.