logo标签列表

计算可能是循环的链表中节点的数量

algorithmlinked-list
6

这里有一个问题，来自Sedgwick在他的优秀著作《Java算法》中（第3.54题）

给定单向链表中的一个节点链接，该链表不包含空链接（即每个节点要么链接到自身，要么链接到列表中的另一个节点），确定不同节点的数量，而不修改任何节点并且使用不超过常数内存空间。

如何做到呢？使用乌龟和兔子算法一次扫描整个链表来判断它是否以任何方式为循环，并再次扫描以找出列表何时变成循环状态，然后再次扫描以计算到达此位置的节点数? 对我来说听起来有点暴力，我想可能还有更优雅的解决方案。

4个回答
7

龟兔赛跑算法可以同时给出循环长度和循环开始前的节点数（分别为λ和μ）。

哈哈，我正在构思一个复杂的答案，基于我的洞察力，乌龟和兔子相遇所需的步数提供了关于循环长度的信息。但是，我应该早点查一下资料。 - Joren
+1。但是你的算法时间复杂度是多少？找到循环O(lambda + u)，找到循环长度O(lambda)，找到颈部长度O(lambda * u)。总体而言，假设N = min(lambda,u)，它仍然是O(N^2)。有没有比二次更好的方法？ - Akusete
@Akusete：什么？该算法在O(λ+μ)时间内给出λ和μ，答案是λ+μ。 - Artelius
2
1

看看这个：链表中的循环问题

指针标记：在实践中，使用C结构实现链接 列表至少需要一个指针；在C语言中，这样的结构需要4字节对齐。因此， 最低有效位是零。当遍历列表时，您可以通过翻转最低有效位来将指针标记为已遍历。 第二次遍历是为了清除这些位。

1
问题陈述了您应该“确定不修改任何节点的不同节点数。”即使这不是一个要求，这个解决方案也有点可疑，因为它过于依赖实现细节，而且不具备语言无关性。 - jason
@Jason：谁在乎呢？我更喜欢一个快速算法（适合我的环境）而不是适用于更多语言的算法。我并不是说这个答案描述了一个快速算法，只是一般来说，算法的性能比可移植性更重要。 - Artelius
1
@Jason，是的，它暂时修改了节点。无论如何，我知道这不是最好的解决方案，但我认为这是一个有趣的解决方案。 - Nick Dandoulakis
是的，我们使用了那两个最低位来实现延迟按需加载指针！但这是另一个故事了。 - AnthonyLambert
-4

只需记住你曾经去过哪里，如果你回到同一个节点，那么游戏就结束了。

尝试将条目存储在二叉树中，您的时间复杂度为O（N * log（N）），空间复杂度为O（N）

编辑

如果您不按指数顺序链接存储每个节点，则可以使用Log（N）空间复杂度。这意味着您存储第1、2、4、8、16个节点，然后如果您被击中，则必须从该点继续。此方法的时间复杂度为N * Log（n）^ 2

但您只能使用恒定的空间 - Tom
log(N) 几乎是常数空间，每个硬盘/内存世界上 100 个条目足以 :D - Luka Rahne
4
抱歉，但是O(log N)和O(1)空间复杂度相差很远，两者并不接近。 - jason
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接