下面是使用Floyd慢速算法发现列表中存在循环后的代码。
我们如何确定begin和tortoise会在循环开始时相遇？
Node begin = head;
tortoise = tortoise.next;
while (begin != tortoise) {
begin = begin.next;
if (tortoise.next == begin) { // Find the position of the loop and mark the node as null
tortoise.next = null;
return;
}
tortoise = tortoise.next;
}
如有任何帮助，我们将不胜感激!
最佳答案
让我们看看您发布的代码之前的第一部分。
考虑
- 慢指针(乌龟)和快指针(野兔)。快指针移动两次 慢速指针的速度，因此当慢速指针移动了距离“d”时，快速指针也移动了 距离“2d”。
- 从起点到交点的长度为x(参见图表)。
- 它们在距交点长度为 y 的随机点处相遇(参见图表)。
- 从交汇点到交点的长度为 z(参见图表)。
- 循环长度为 y+z；
- 当慢与快相遇时。 Slow 已走过距离 x+y (比如 d)
快速移动了距离 x+y+z+y (将是 2*d)
2*d=x+2y+z
2(x+y)=x+2y+z
2x+2y=x+2y+z
x=z(已证明)
现在来看您发布的代码。
因为已经证明，在第一个交点之后 x 将等于 z(假定野兔的速度是乌龟的两倍)，然后从开头移动一个指针，然后从第一个交点移动一个指针到交点(即环形)。
关于java - 关于链表去环逻辑的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58217211/