我读到了链表检测算法中的循环 ，我怀疑
1）如何检测“会议元素”。例如，在以下情况下 - 如何检测会议在第三个元素？
2）如何检测列表的长度（以上情况 - 6）
运行时间 O(n) 和内存 O(1)中的两个问题。
问问题
2661 次
3 回答
9
使用龟兔算法（弗洛伊德循环检测），我们可以在给定的列表中找到循环。
即如果我们移动两个指针，一个速度为 1，另一个速度为 2，如果链表有循环，它们最终会相遇。为什么？想想两辆汽车在一条赛道上行驶——速度快的汽车总会超过速度慢的汽车！
这里棘手的部分是找到循环的开始。想象一下，作为一个类比，两个人在赛道上比赛，一个人跑的速度是另一个人的两倍。如果他们从同一个地方出发，他们下一次见面是什么时候？他们将在下一圈开始时相遇。
因此，在确定循环之后，如果我们将 n1 移回 Head 并将 n2 保持在 MeetingPoint，并以相同的速度移动它们，它们将在 LoopStart(Meeting Element) 相遇。
然后，要找到长度，在将 n1 移回头部时定义一个长度变量。现在在每次移动时增加长度变量。确定 LoopStart 后，保持 n1 ptr 不变，每次移动都移动 n2 ptr 和 inc 长度。当 n2->next == n1 时，返回长度。
这将有运行时间 O(N)，空间复杂度 O(1)
于 2012-09-06T12:11:56.630 回答
0
当使用 Floyd 的循环查找算法时，快速和慢速引用不会在第三个元素处相遇，而是在第四个元素处相遇。它们的位置从 (1,2) 开始，移动如下：(1,2) -> (2,4) -> (3,6) -> (4,4)。
我认为，要找出循环的精确位置，您需要 O(n) 空间和 O(n) 时间。
于 2012-09-06T11:31:31.343 回答
-1
我认为您不能仅使用 O(1) 工作内存在 O( n ) 时间内完成此操作。
“会议元素”（循环开始）有n 个不同的候选对象，而在 O(1) 内存中，您只能记录固定数量的候选对象。如果您可以多次绕过该结构，这不是问题，但如果您只能在每次遍历中检查固定数量的节点，您需要遍历该结构n次，总共花费 O( n² ) 时间.
直接的解决方案是放弃 O(1) 内存要求。绕过循环一次并将指向节点的指针存储在哈希表中，直到遇到重复条目。预期时间 O( n )，内存使用量 O( n )。
于 2012-09-06T11:33:45.843 回答