野兔和乌龟算法。为什么链接列表的碰撞点和头部与循环开始的距离相同?

问题描述 投票:0回答:1

在Cracking the Coding访谈书中,给出了如何找到循环开头在链表中的位置的以下说明:

有一个FastRunner推进两个步骤,SlowRunner推进两个步骤(每单位时间)。

k - >循环之前的节点数量K = mod(k, LOOP_SIZE) - >当慢速跑步者刚刚击中循环中的第一个节点时,快速跑步者在循环内的步数。

FastRunner是LOOP_SIZE - K,仅次于SlowRunner,FastRunner以每单位时间1步的速度赶上SLowRunner。

他们在LOOP_SIZE - K之后相遇,此时他们将在循环的头部之前成为K步。

为了找到循环的开始,作者说:从K = mod(k, LOOP_SIZE)开始,我们可以说k = K + M * LOOP_SIZE(对于任何整数M),然后在这里我迷路了,她说这是正确的说它是k循环中的节点开始。

据我所知,碰撞点是从循环开始的K个节点,但为什么它也是k个节点?她怎么发现K = k?

algorithm
1个回答
3
投票

井K是循环内的节点数,“跳过”的速度越快,直到慢速进入循环。速度比较慢的速度快2倍,因此总共需要跳过2 * k个节点的速度越快(因为较慢的节点需要k才能进入循环)。所以它在循环中所做的跳跃次数是K=2*k-k(所有跳跃减去它为了进入循环所做的跳跃)所以K == k

© www.soinside.com 2019 - 2024. All rights reserved.