我知道龟兔赛跑结束了一个循环的存在，但是如何将乌龟移动到链表的开头，同时将兔子保持在会场，然后一次移动两个步骤使它们在起点相遇周期？
问问题
90487 次
23 回答
372
让我试着用我自己的话来澄清一下Wikipedia - Tortoise_and_hare提供的循环检测算法。
这个怎么运作
让我们有一只乌龟和一只野兔（指针的名称）用一个循环指向列表的开头，如上图所示。
让我们假设，如果我们一次移动乌龟 1 步，一次移动兔子 2 步，它们最终会在一点相遇。让我们首先证明这个假设是正确的。
该图显示了一个带有循环的列表。循环的长度为n，我们最初m离循环只有几步之遥。另外，假设集合点距离循环开始只有几步之遥，当乌龟走完全部步数k时，龟兔赛跑。i（到那时，野兔会采取2i全部步骤。）。
必须满足以下 2 个条件：
1) i = m + p * n + k
2) 2i = m + q * n + k
第一个说乌龟移动i步骤，在这些i步骤中，它首先进入循环。然后它通过p一些正数的循环时间p。最后，它会遍历k更多节点，直到遇到野兔。
野兔也是如此。它移动2i步骤，在这些2i步骤中它首先进入循环。然后它通过q一些正数的循环时间q。最后，它会遍历k更多节点，直到遇到乌龟。
由于兔子以两倍于乌龟的速度行进，当它们到达汇合点时，两者的时间是恒定的。
所以通过使用简单的速度、时间和距离关系，
2 ( m + p * n + k ) = m + q * n + k
=> 2m + 2pn + 2k = m + nq + k
=> m + k = ( q - 2p ) n
在m, n, k, p, 中q，前两个是给定列表的属性。如果我们可以证明 , 至少有一组值k，这使得这个等式成立q，p我们就证明了这个假设是正确的。
一组这样的解决方案如下：
p = 0
q = m
k = m n - m
我们可以验证这些值的工作方式如下：
m + k = ( q - 2p ) n
=> m + mn - m = ( m - 2*0) n
=> mn = mn
对于这个集合，i是
i = m + p n + k
=> m + 0 * n + mn - m = mn
当然，您应该看到这不一定是最小i的可能。也就是说，龟兔赛跑可能已经见过很多次了。但是，由于我们表明它们至少在某个时间点相遇，因此我们可以说该假设是正确的。因此，如果我们将其中一个移动 1 步，而将另一个移动 2 步，它们将不得不相遇。
现在我们可以进入算法的第二部分，即如何找到循环的开始。
周期开始
一旦乌龟和兔子相遇，让我们将乌龟放回列表的开头，并将兔子放在它们相遇的地方（k距离循环开始只有几步之遥）。
假设是，如果我们让它们以相同的速度移动（两者都移动一步），那么它们第一次再次相遇将是循环的开始。
让我们证明这个假设。
让我们首先假设一些预言告诉我们是什么m。
然后，如果我们让它们移动m + k步骤，乌龟将不得不到达它们最初遇到的点（k距离循环开始的步骤 - 见图）。
之前我们展示了m + k = (q - 2p) n.
由于m + kstep 是 cycle length 的倍数n，因此 hare 同时会经过循环 ( q-2p) 次并返回到同一点（k距离循环开始有几步）。
现在，m + k如果我们让它们只移动步，而不是让它们移动步，m乌龟将到达循环开始处。Hare距离完成 ( ) 旋转还差k几步。q-2p由于它在周期开始之前开始k步骤，因此野兔必须在周期开始时到达。
结果，这解释了他们必须在第一次经过一些步骤后在循环开始时相遇（第一次，因为乌龟在m步骤之后才到达循环并且它永远看不到已经在循环）。
现在我们知道，我们需要移动它们直到它们相遇的步数原来是从列表开始到循环开始的距离，m。当然，算法不需要知道是什么m。它只会一步一步地移动乌龟和兔子，直到它们相遇。汇合点必须是循环起点，步数必须是m到循环起点的距离 ( )。假设我们知道列表的长度，我们还可以计算m从列表长度中减去循环的长度。
于 2011-05-24T12:56:28.027 回答
142
参考这张图片：
slowPointer 在相遇前经过的距离= x + y
fastPointer 在会面前经过的距离= (x + y + z) + y = x + 2y + z
由于 fastPointer的行进速度是 slowPointer 的两倍，并且在到达会合点时两者的时间都是恒定的。
所以通过使用简单的速度、时间和距离关系 2(x+y)= x+2y+z => x+2y+z = 2x+2y => x=z
因此，通过将slowPointer移动到链表的开头，并使 slowPointer 和 fastPointer 一次移动一个节点，它们都具有相同的覆盖距离。
它们将到达链表中循环开始的点。
于 2015-08-24T19:50:02.920 回答
93
这是Floyd 的循环检测算法。你在问算法的第二阶段——一旦你找到了一个属于循环的节点，如何找到循环的开始？
在弗洛伊德算法的第一部分，兔子每走一步，乌龟就移动两步。如果龟兔赛跑，就有一个循环，相遇点是循环的一部分，但不一定是循环中的第一个节点。
当乌龟和兔子相遇时，我们找到了最小的 i（乌龟走的步数），使得 X i = X 2i。让 mu 表示从 X 0到循环开始的步数，让 lambda 表示循环的长度。然后 i = mu + a lambda 和 2i = mu + b lambda，其中 a 和 b 是整数，表示龟兔赛跑了多少次。从第二个方程中减去第一个方程得到 i = (ba)*lambda，所以 i 是 lambda 的整数倍。 因此，X i + mu = X mu。X i代表龟兔赛跑的交汇点。如果将乌龟移回起始节点 X0，让龟兔以同样的速度继续前进，经过 mu 个额外的步骤，乌龟将达到 X mu，而兔子将达到 X i + mu = X mu，因此第二个交汇点表示开始循环。
于 2010-05-29T19:37:57.903 回答
82
Old Monk 的简单且被低估的答案解释了当快跑者只完成一个完整的循环时找到循环。在这个答案中，我解释了快跑者在慢跑者进入循环之前多次运行循环的情况。
使用相同的图像：
假设快速跑步者在慢速和快速相遇之前已经运行了m次循环。这意味着：
- 慢跑距离：x + y
- 快速运行的距离：x + m(y + z) + y即他们相遇的额外y
因为快跑的速度是慢跑的两倍，而且他们跑的时间是一样的，这意味着如果我们把慢跑的距离加倍，我们就会得到快跑的距离。因此，
- 2(x + y) = x + m(y + z) + y
求解 x 给出，
x = (m - 1)(y + z) + z
在实际场景中，这意味着x = (m - 1)完整循环运行 + 额外距离z。
因此，如果我们将一个指针放在列表的开头，而将另一个指针留在会合点，那么以相同的速度移动它们将导致循环内指针完成m - 1次循环运行，然后遇到另一个指针在循环开始处。
于 2016-03-25T06:08:56.430 回答
14
这非常非常简单。你可以从相对速度的角度来思考。如果兔子移动了两个节点，乌龟移动了一个节点，相对于乌龟，兔子移动了一个节点（假设乌龟处于静止状态）。所以，如果我们在循环链表中移动一个节点，我们肯定会在那个点再次相遇。
在找到循环链表内部的连接点之后，现在问题被简化为找到两个链表的交点问题。
于 2014-10-26T04:21:13.460 回答
10
在第一次碰撞时，乌龟移动了m+k步，如上所示。野兔的移动速度是乌龟的两倍，这意味着野兔移动了2(m+k)步。从这些简单的事实我们可以得出下图。
此时，我们将乌龟移回起点，并声明兔子和乌龟都必须一次移动一步。根据定义，经过m步后，乌龟将处于循环的开始。野兔会在哪里？
野兔也将处于周期的开始。从第二张图可以清楚地看出：当乌龟被移回起点时，野兔进入最后一个循环的k步。经过m步后，兔子将完成另一个循环并与乌龟相撞。
于 2014-08-20T00:06:16.160 回答
9
方法：
有两个指针：
- 一次移动一个节点的慢速指针。
- 一次移动两个节点的快速指针。
如果两个指针相遇，则证明存在循环。一旦他们相遇，其中一个节点将指向头部，然后两个节点一次前进一个节点。他们将在循环开始时相遇。
理由： 当两个人沿着环形轨道走时，其中一个人的速度是另一个人的两倍，他们在哪里相遇？正是他们开始的地方。
现在，假设跑得快的人k在n一圈中领先一步。他们会在哪里见面？正好在n-k台阶上。当慢跑者跑过(n-k)台阶时，快跑者会跑过k+2(n-k)台阶。（即k+2n-2k步骤即2n-k步骤）。即(n-k)步骤（路径是圆形的，我们不关心它们相遇的轮数；我们只对它们相遇的位置感兴趣）。
现在，跑得快的人是如何一开始就领先k一步的呢？因为慢跑者花了很多步才能到达循环的开始。所以循环的开始距离头节点 k 步。
注意：两个指针相遇的节点k距离循环开始（循环内部）只有几步之遥，而头节点也k距离循环开始只有几步之遥。因此，当我们让指针从 bot 这些节点以 1 步的相同速度前进时，它们将在循环开始时相遇。
我相信这很简单。请让我知道是否有任何部分模棱两可。
于 2014-05-09T11:48:46.253 回答
5
好的，假设兔子和乌龟在距离循环开始 k 步的点相遇，循环开始前的步数是 mu，循环的长度是 L。
所以现在在集合点->
乌龟覆盖的距离 = mu + a*L + k - 公式 1
（到达循环开始所采取的步骤 + 覆盖循环的“a”次迭代所采取的步骤 + 从循环开始的 k 步骤）（其中 a 是某个正常数）
野兔覆盖的距离 = mu + b*L + k - 公式 2
（到达循环开始所采取的步骤 + 覆盖循环的“b”次迭代所采取的步骤 + 从循环开始的 k 步骤）（其中 b 是某个正常数，b>=a）
所以野兔所覆盖的额外距离是 = 等式 2 - 等式 1 = (ba)*L
请注意，这个距离也等于乌龟到起点的距离，因为兔子的移动速度是乌龟的 2 倍。这可以等同于“mu+k”，如果我们不包括循环的多次遍历，这也是会合点到起点的距离。
因此，mu + k = (ba)*L
因此，从这一点开始的 mu 步将导致回到循环的开始（因为已经从循环开始的 k 步到达汇合点）。这可能发生在同一周期或任何后续周期中。因此，现在如果我们将乌龟移动到链表的开头，它将采取 mu 步到达循环的起点，而兔子也将采取 mu 步到达循环的起点，因此它们都会在循环的起点。
PS老实说，我的脑海里和原始海报有同样的问题，我读了第一个答案，他们确实清除了一些东西，但我无法清楚地得到最终结果，所以我试着用自己的方式做，发现更容易理解。
于 2013-07-22T06:38:19.863 回答
4
将问题简化为循环问题，然后回到最初的问题
我觉得下面的解释更直观。
取两个从头部 ( O ) 开始的指针（1 = 乌龟和2 = 野兔） ，1的步长为1，2的步长为2。想想1到达该循环的开始节点（A）的那一刻。
我们要回答以下问题“当 1 在 A 中时 2 在哪里？” .
所以,
OA = a是一个自然数 (a >= 0)。但它可以写成以下方式：a = k*n + b，其中a, k, n, b are natural numbers：n= 周期长度k >= 0= 常数0 <= b <= n-1
这意味着
b = a % n。例如：如果
a = 20和n = 8=>k = 2和b = 4因为20 = 2*8 + 4.1所经过的距离是
d = OA = a = k*n + b。但同时，2个封面D = 2*d = d + d = OA + d = OA + k*n + b。这意味着当2在 A 中时，它必须覆盖k*n + b。如您所见，k是圈数，但在这些圈之后，2将远离A。所以，当1在 A 中时，我们找到了2的位置。让我们称该点为， where 。BAB = b
现在，我们将问题简化为一个圆圈。问题是“集合点在哪里？” . 那个C在哪里？
在每一步中，2都会减少与1的距离
1（假设是米），因为1距离2 更远，但1同时2更接近1。2因此，交点将是1和2之间的距离为零时。这意味着2减少了
n - b距离。为了实现这一点，1会做n - b步骤，而2会做2*(n - b)步骤。因此，交点将
n - b远离A（顺时针方向），因为这是1所覆盖的距离，直到它遇到2。=> C和A之间的距离是CA = b，因为AC = AB + BC = n - b和CA = n - AC。不要以为AC = CA，因为AC距离不是一个微不足道的数学距离，它是A和C之间的步数（其中A是起点，C是终点）。现在，让我们回到初始模式。
我们知道
a = k*n + b和CA = b。我们可以采用 2 个新指针1'和1''，其中1'从头部（O）开始，1''从交点（C）开始。
当1'从O到A时，1''从C到A并继续完成
k圈数。所以，交点是A。
于 2015-10-15T09:40:21.107 回答
4
使用高中教授的相对速度概念的简单解释- 物理 101 / 运动学讲座。
让我们假设从链表开始到圆开始的距离是
x跳数。让我们将圆的起点称为点X（大写字母 - 见上图）。还让我们假设圆的总大小是 N 跳。兔子的速度 = 2 * 乌龟的速度。所以
1 hops/sec分别2 hops/sec是当乌龟到达圆圈的起点时
X，兔子必须进一步x跳离图中的点Y。（因为兔子的距离是乌龟的两倍）。因此，从 X 到 Y 顺时针方向的剩余弧的长度将是
N-x。这也恰好是兔子和乌龟能够相遇的相对距离。假设这个相对距离将被及时覆盖，t_m即相遇的时间。相对速度(2 hops/sec - 1 hops/sec)即1 hops/sec。因此，使用相对距离 = 相对速度 X 时间，我们得到t=N-x秒。所以它需要N-x到达乌龟和兔子的交汇点。现在以
N-x秒为单位，以1 hops/sec最快的速度，较早到达点的乌龟X将覆盖Nx跳到达会合点M。因此，这意味着会合点M位于N-x从 = 逆时针方向的跃点处X（这进一步暗示）=>从点到顺时针方向还有x距离。MX但
x也是X从链表开始到到达点的距离。现在，我们不在乎
x对应的跳数是多少。如果我们将一只乌龟放在 LinkedList 的开头，一只乌龟放在会合点M，让它们跳跃/行走，那么它们将在 point 相遇X，这是我们需要的点（或节点）。
于 2017-05-25T05:17:23.147 回答
3
调用距离是指针遵循的链接数，时间是算法将慢速指针移动一个链接和快速指针移动两个链接所花费的迭代次数。在长度为 C 的循环之前有 N 个节点，用循环偏移量 k=0 到 C-1 标记。
要到达循环的开始，慢需要 N 时间和距离。这意味着快速在循环中需要 N 距离（N 到达那里，N 旋转）。所以在时间 N，slow 在周期偏移 k=0 处，fast 在周期偏移 k=N mod C 处。
如果 N mod C 为零，则慢速和快速现在匹配，并且在时间 N 和循环位置 k=0 处找到循环。
如果 N mod C 不为零，那么现在快必须赶上慢，在时间 N 是循环中落后的 C-(N mod C) 距离。
由于每 1 次慢速快速移动 2 次，因此每次迭代将距离减少 1，因此这花费的额外时间与时间 N 时快速和慢速之间的距离一样多，即 C-(N mod C)。由于慢从偏移量 0 移动，这也是它们相遇的偏移量。
因此，如果 N mod C 为零，则阶段 1 在循环开始的 N 次迭代后停止。否则，阶段 1 在 N+C-(N mod C) 次迭代后在偏移量 C-(N mod C) 处停止进入循环。
// C++ pseudocode, end() is one after last element.
int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
t += 1;
fast = next(fast);
if (fast == end()) return [N=(2*t-1),C=0];
fast = next(fast);
if (fast == end()) return [N=(2*t),C=0];
slow = next(slow);
if (*fast == *slow) break;
}
好的，所以第 2 阶段：slow 需要 N 多步才能进入循环，此时 fast（现在每个时间步移动 1 个）位于 (C-(N mod C)+N) mod C = 0。所以他们相遇在第 2 阶段之后的周期开始时。
int N = 0;
slow = begin();
for (;;) {
if (*fast == *slow) break;
fast = next(fast);
slow = next(slow);
N += 1;
}
为了完整起见，第 3 阶段通过再次移动循环来计算循环长度：
int C = 0;
for (;;) {
fast = next(fast);
C += 1;
if (fast == slow) break;
}
于 2018-12-06T07:02:26.167 回答
3
已经有很多答案了，但我曾经为此想出了一个图表，这对我来说更直观。也许它可以帮助其他人。
对我来说，主要的惊喜时刻是：
将T（乌龟）拆分为T1（预循环）和T2（循环内）。
从H中减去T，它们在视觉上重叠。剩下的（H - T = H'）等于T。
- 剩下的数学很简单。
于 2019-03-18T18:15:38.287 回答
3
- 在循环之前有 k 步。我们不知道 k 是什么，也不需要找出来。我们可以只用 k 抽象地工作。
--经过k步
----- T 处于循环开始
----- H是k步进入循环（他总共走了2k，因此k进入循环）
** 它们现在是 loopsize - k 分开
（请注意，k == K == mod(loopsize, k) - 例如，如果一个节点在 5 个节点的循环中分 2 步，那么它也是 7、12 或 392 步，所以循环的大小与 k 无关考虑到。
由于它们以每单位时间 1 步的速度相互追赶，因为其中一个的移动速度是另一个的两倍，因此它们将在 loopsize - k 处相遇。
这意味着它将需要 k 个节点到达循环的开始，因此从 head 到 cyclestart 的距离以及从碰撞到 cyclestart 的距离是相同的。
所以现在在第一次碰撞后将 T 移回头部。如果您以 1 的速率移动，T 和 H 将在循环开始时相遇。（两者都在 k 步中）
这意味着该算法是：
- 从头部移动 T = t.next 和 H.next.next 直到它们碰撞（T == H）（有一个循环）
//通过计算循环的长度来处理k=0或T和H在循环头部相遇的情况
-- 用计数器移动 T 或 H 来计算循环的长度
-- 将指针 T2 移动到列表的头部
--移动循环步骤的指针长度
--将另一个指针H2移到head
-- 将 T2 和 H2 串联移动，直到它们在循环开始时相遇
而已！
于 2017-03-05T23:36:26.760 回答
3
如图所示，如果指针在点P相遇，距离Z+Y就是点P，X+Y也是点P，即Z=X。这就是为什么保持从 P 移动一个指针并从 start(S) 移动另一个指针直到它们相遇，这意味着将相等的距离（Z 或 X）移动到同一点 M（Z 到 P 的距离和 X 到 S 的距离）将是循环的开始。简单的！
于 2018-07-17T06:21:37.430 回答
2
通过以上所有分析，如果您是一个通过示例学习的人，我会尝试写一个简短的分析和示例来帮助解释其他人试图解释的数学。开始了！
分析：
如果我们有两个指针，一个比另一个快，并将它们一起移动，它们最终将再次相遇以指示一个循环或 null 以指示没有循环。
为了找到循环的起点，让...
m是从头部到循环开始的距离；d是循环中的节点数；p1是较慢指针的速度；p2是更快指针的速度，例如。2 表示一次通过两个节点。观察以下迭代：
m = 0, d = 10: p1 = 1: 0 1 2 3 4 5 6 7 8 9 10 // 0 would the start of the cycle p2 = 2: 0 2 4 6 8 10 12 14 16 18 20 m = 1, d = 10: p1 = 1: -1 0 1 2 3 4 5 6 7 8 9 p2 = 2: -1 1 3 5 7 9 11 13 15 17 19 m = 2, d = 10: p1 = 1: -2 -1 0 1 2 3 4 5 6 7 8 p2 = 2: -2 0 2 4 6 8 10 12 14 16 18
从上面的示例数据中，我们可以很容易地发现，每当更快和更慢的指针相遇时，它们就m距离循环的开始只有几步之遥。要解决此问题，请将较快的指针放回头部，并将其速度设置为较慢指针的速度。当他们再次相遇时，节点就是循环的开始。
于 2014-11-14T01:14:49.270 回答
1
我不认为这是真的，当他们相遇时，这就是起点。但是是的，如果另一个指针（F）在之前的交汇点处，那么该指针将位于循环的结尾而不是循环的开头，并且从列表开头开始的指针（S）将结束在循环的开始。例如：
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8
Meet at :16
Start at :8
public Node meetNodeInLoop(){
Node fast=head;
Node slow=head;
fast=fast.next.next;
slow=slow.next;
while(fast!=slow){
fast=fast.next;
fast=fast.next;
if(fast==slow) break;
slow=slow.next;
}
return fast;
}
public Node startOfLoop(Node meet){
Node slow=head;
Node fast=meet;
while(slow!=fast){
fast=fast.next;
if(slow==fast.next) break;
slow=slow.next;
}
return slow;
}
于 2013-10-06T14:21:16.690 回答
1
可以说，
N[0] is the node of start of the loop,
m is the number of steps from beginning to N[0].
我们有 2 个指针 A 和 B，A 以 1x 速度运行，B 以 2x 速度运行，都从头开始。
当 A 到达 N[0] 时，B 应该已经在 N[m] 中。（注：A 使用 m 步到达 N[0]，B 应该再进一步 m 步）
然后，A再跑k步与B碰撞，即A在N[k]，B在N[m+2k]（注意：B应该从N[m]开始跑2k步）
A分别在N[k]和N[m+2k]处碰撞B，表示k=m+2k，因此k = -m
因此，要从 N[k] 循环回到 N[0]，我们还需要 m 个步骤。
简单地说，我们只需要在找到碰撞节点后再运行 m 步即可。我们可以有一个从开始运行的指针和一个从碰撞节点运行的指针，它们将在 m 步后在 N[0] 处相遇。
因此，伪代码如下：
1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6
于 2015-12-15T07:40:34.983 回答
1
用图表来解决这个问题会有所帮助。我试图在没有方程式的情况下解释这个问题。
- 如果我们让兔子和乌龟跑一圈，然后兔子跑两次乌龟，那么在一圈结束时，兔子乌龟会跑到一半。在两圈结束时，兔龟会跑完一圈，它们都会相遇。这适用于所有速度，例如如果兔子跑了 3 次，兔子 1 圈等于乌龟的 1/3，所以在 3 圈结束时，兔子乌龟会跑完 1 圈然后相遇。
- 现在，如果我们在循环之前开始它们 m 步，那么这意味着更快的野兔正在循环中提前开始。因此，如果乌龟到达循环的开始，兔子会提前 m 步循环，当它们相遇时，它将在循环开始前 m 步。
于 2017-09-03T07:04:45.597 回答
0
在花了两个小时试图阅读所有答案后，我在 leetcode 上找到了这条评论。可以肯定地说，它拯救了我的夜晚。
于 2021-09-19T05:54:35.007 回答
0
我看到大多数答案对此给出了数学解释“如何将乌龟移动到链表的开头，同时将野兔保持在相遇地点，然后一次移动两个步骤使它们在循环的起点相遇？ ”
以下方法也与幕后的弗洛伊德循环检测一样，但原理很简单，但代价是 O(n) 内存。
我想添加一个更简单的方法/理由来找到周期的开始。由于没有在任何地方提及此方法，因此我在这里进行了测试：https : //leetcode.com/problems/linked-list-cycle-ii/ 它通过了所有测试用例。
让我们考虑一下，我们已经获得了 LinkedList 的头部引用。
public ListNode detectCycle(ListNode head) {
// Consider a fast pointer which hops two nodes at once.
// Consider a slow pointer which hops one node at once.
// If the linked list contains a cycle,
// these two pointers would meet at some point when they are looping around the list.
// Caution: This point of intersection need not be the beginning of the cycle.
ListNode fast = null;
ListNode slow = null;
if (head != null) {
if (head.next != null) {
fast = head.next.next;
slow = head;
} else {
return null;
}
}
while (fast != null && fast.next != null) {
// Why do we need collection here? Explained below
Set<ListNode> collection = new HashSet<>();
if (fast == slow) {
// Once the cycle is detected,
we are sure that there is beginning to the cycle.
// In order to find this beginning,
// 1. move slow pointer to head and keep fast pointer at
the meeting point.
// 2. now while moving slow and fast pointers through a
single hop, store the slow reference in a collection.
// 3. Every time you hop the fast pointer, check the fast
pointer reference exits in that collection.
// Rationale: After we moved slow pointer to the head,
we know that slow pointer is coming behind the fast
pointer, since collection is storing all nodes from the
start using slow pointer, there is only one case we get
that fast pointer exists in the collection when slow
pointer started storing the nodes which are part of the
cycle. Because slow pointer can never go ahead of fast
pointer since fast pointer already has an head-start, at
the same time, the first occurence will always be of the
starting point of the cycle because slow pointer can't
go ahead of fast pointer to store other nodes in the
cycle. So, the moment we first find fast pointer in that
collection means, that is the starting point of the
cycle.
slow = head;
collection.add(slow);
while (!collection.contains(fast)) {
slow = slow.next;
collection.add(slow);
fast = fast.next;
}
return fast;
}
fast = fast.next.next;
slow = slow.next;
}
return null;
}
于 2021-05-14T06:39:28.560 回答
-1
It is actually easy to prove that they both will meet at the starting point, if you consider the maths behind the meeting point.
Firstly let m denote the starting point of cycle in the linked list , and n denote the length of the cycle . Then for the hare and tortoise to meet , we have :
( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)
Stating this more mathematically :
(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n
so they will meet at time t which should be a multiple of length of cycle . This means that they meet at a location, which is
(t-m) modulo n = (0-m) modulo n = (-m) modulo n .
So now coming back to the question , if you move one pointer from the start of the linked list , and another from the intersection point , after m steps we will have the hare (which is moving inside the cycle) come to a point which is ((-m) + m) modulo n = 0 modulo n which is nothing but the starting point of the cycle.So we can see that after m steps it comes to the start of the cycle and the tortoise will meet it there as it will traverse m steps from the start of the linked list.
As a side note ,we can also calculate the time of their intersection in this way : The condition t = 0 modulo n tells us that they will meet at a time which is a multiple of cycle length , and also t should be greater than m as they would meet in the cycle . So time taken will be equal to the first multiple of n which is greater than m .
于 2013-08-25T19:40:45.887 回答
-1
我知道这个问题已经有一个公认的答案，但我仍然会尝试以流畅的方式回答。认为 ：
The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path.
Speed of tortoise : v
Speed of hare : 2*v
Point where both meet is at a distance 'x + b - k' from the starting point.
现在，让兔子和乌龟在时间“t”之后相遇。
观察：
如果，乌龟行进的距离 = v*t = x + (bk)（比方说）
然后，野兔经过的距离 = 2*v*t = x + (b - k) + b（因为野兔已经穿过循环部分一次）
现在，那里的会议时间是一样的。
=> x + 2*b - k = 2* (x + b - k)
=> x = k
这当然意味着没有循环的路径的长度与循环的起点到两者相交点的距离相同。
于 2011-09-21T15:39:38.610 回答
-1
于 2019-09-08T09:47:13.173 回答