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

Question

我读了关于链表检测算法的循环 ,我怀疑

1)如何检测"会议元素".例如,在以下情况中 - 如何检测会议是否在第3个元素？

2)如何检测列表的长度(如果超过 - 6)

运行时间O(n),存储器O(1)中的两个问题.

Answer 1

使用tortoise-hare算法(floyd的循环检测),我们可以在给定的列表中找到循环.

即如果我们移动两个指针,一个速度为1,另一个速度为2,如果链表有循环,它们将会结束.为什么？想想两辆在赛道上行驶的汽车 - 速度越快的汽车总会越过慢速汽车!

这里棘手的部分是找到循环的开始.想象一下,作为一个类比,两个人在赛道上比赛,一个赛跑的速度是另一个赛车的两倍.如果他们在同一个地方开始,他们下一次会什么时候见面？接下来他们将在下一圈开始时见面.

因此,在识别循环之后,如果我们将n1移回Head并在MeetingPoint保持n2,并以相同的速度移动它们,它们将在LoopStart(会议元素)处相遇.

然后,为了找到长度,当移动n1回到头部时定义一个长度变量.现在在每次移动时增加长度变量.在确定LoopStart之后,保持n1 ptr,并为每次移动移动n2 ptr和inc长度.当n2-> next == n1时,返回长度.

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