algorithm - 链表循环 - 循环起始元素和列表长度

Question

我读到了 loop in linked list detection algorithm我怀疑

1) 如何检测“ session 元素”。例如，在下面的情况下 - 如何检测 meeting 在第 3 个元素？

2) 如何检测列表的长度(在上述情况下 - 6)

这两个问题的运行时间为 O(n)，内存为 O(1)。

Answer 1

使用龟兔赛跑算法(弗洛伊德循环检测)，我们可以在给定的列表中找到循环。

即如果我们移动两个指针，一个速度为 1，另一个速度为 2，如果链表有环，它们最终会相遇。为什么？想一想两辆车在赛道上行驶——快车总会超过慢车!

这里棘手的部分是找到循环的起点。想象一下，打个比方，两个人绕着一条跑道跑，一个人跑的速度是另一个人的两倍。如果他们从同一个地方出发，他们下次见面是什么时候？他们将在下一圈开始时相遇。

因此，在确定循环后，如果我们将 n1 移回 Head 并将 n2 保持在 MeetingPoint，并以相同的速度移动它们，它们将在 LoopStart(Meeting Element)处相遇。

然后，为了找到长度，当将 n1 移回 head 时，定义一个长度变量。现在每次移动都会增加长度变量。在确定 LoopStart 之后，保持 n1 ptr 不变，并移动 n2 ptr 和每次移动的 inc 长度。 当n2->next == n1时，返回长度。

这将有运行时间 O(N)，空间复杂度 O(1)