有没有人知道一个算法来查找链表是否只使用两个变量来遍历列表.假设您有一个链接的对象列表,它与哪种类型的对象无关.我在一个变量中有一个指向链表头部的指针,我只有一个其他变量来遍历列表.
所以我的计划是比较指针值以查看是否有任何指针相同.该列表的大小有限,但可能很大.我可以将两个变量都设置为头部,然后用另一个变量遍历列表,总是检查它是否等于另一个变量,但是,如果我确实打了一个循环,我将永远不会离开它.我认为它与遍历列表和比较指针值的不同速率有关.有什么想法吗？
确定链表是否有循环的最佳(暂停)算法是什么？
[编辑]对时间和空间的渐近复杂性的分析将是甜蜜的,因此可以更好地比较答案.
[编辑]原始问题没有解决超过1的节点,但有一些关于它的讨论.这个问题更像是"在有向图中检测周期的最佳算法".
可能重复:
查找链接列表中是否存在没有两个指针的循环
如何确定链接列表是否只使用两个内存位置进行循环.
测试链表是否有循环的最佳算法
在准备面试时,我遇到了以下问题:
如何使用额外的空间复杂度O(1)来确定链接列表(任何类型)是否包含循环？您不能假设循环从第一个节点开始(当然,循环不必包含所有节点).
我找不到答案,虽然我觉得这很简单......
这是问题所在,它来自Sedgwick在Java中出色的算法(q 3.54)
给定链接到单链表中不包含空链接的节点(即每个节点链接到自身或列表中的另一个节点)确定不同节点的数量而不修改任何节点并使用不超过常量内存空间.
你怎么做呢？扫描列表一次使用野兔和乌龟算法来确定它是否是任何方式的圆形,然后再次扫描以确定列表变为圆形的位置,然后再次扫描计算到这个位置的节点数？对我来说听起来有点蛮力,我想有更优雅的解决方案.