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