检查链表的循环性
检查链表的循环性
提问于 2008-12-30 10:28:17
我需要一个接受linkedlist作为参数的方法，如果它是循环的或非循环的，则返回true或false。
例如:循环链接列表表示存在指向任何先前节点的节点。我忘了告诉你一些约束，我不能使用任何数据结构或动态内存分配。我只能使用局部变量，算法可以在n个步骤中完成，就像有人对我说的那样(我现在正在考虑使用两个指针？)
回答 3
Stack Overflow用户
回答已采纳
发布于 2008-12-30 10:47:52
我相信你是来找Floyd's Cycle-Finding Algorithm的。有一个比我在here上给出的更好的解释。
还有几个C和方案的实现，以及here上的文档。
Stack Overflow用户
发布于 2008-12-30 10:44:02
这是微不足道的。
previousnodes ← set()
previousnodes.add(firstnode)
currentnode ← firstnode.next
while (currentnode in previousnodes) || (currentnode != null):
previousnodes.add(currentnode)
currentnode ← currentnode.next
when (currentnode = 0) return false
return trueStack Overflow用户
发布于 2011-10-12 18:28:53
我自己发现了这个问题的一个很好的解决方案，并情不自禁地把它贴在这里(尽管我猜最初的帖子现在很可能已经毕业了)。从start节点开始，只需开始反转列表。如果列表不是循环的，则进程将以Null结束，如果列表确实是循环的，则进程将在开始节点结束。因此，这就是一个具有恒定额外空间的线性时间算法。只需再次反转列表，即可恢复原始列表。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/399937
复制相关文章
相似问题
腾讯云开发者
