野兔和乌龟算法。为什么冲突点和链表头在循环开始时位于相同距离？ [英] Hare and tortoise algorithm. Why is the collision spot and head of linked list at the same distance of the start of the loop?

问题描述

在《破解编码》采访书中，对如何找到循环起点在链表中的位置进行了以下说明：

In the Cracking the Coding interview book, it is given the following explanation about the how to find where the beginning of a loop is in a linked list:

有是前进两步的FastRunner和前进两步（每单位时间）的SlowRunner。

There is a FastRunner which advances two steps, and a SlowRunner which advances two steps (per unit of time).

k->循环前的节点数
K = mod（k，LOOP_SIZE）->当慢速跑步者刚好碰到循环中的第一个节点时，快速跑步者进入循环的步数。

k -> number of nodes before loop K = mod(k, LOOP_SIZE) -> number of steps the fast runner is inside the loop when the slow runner just hit the first node in the loop.

FastRunner是 LOOP_SIZE-K 落后于SlowRunner
FastRunner以1的速度赶上SLowRunner

FastRunner is LOOP_SIZE - K steps behind SlowRunner FastRunner catches up to SLowRunner at a rate of 1 step per unit of time.

他们在 LOOP_SIZE-K 之后见面，此时他们将是K步之前

They meet after LOOP_SIZE - K, at this point they will be K steps before the head of the loop.

为了找到循环的起点，作者说：
因为 K = mod （k，LOOP_SIZE），我们可以说 k = K + M * LOOP_SIZE （对于任何整数M），那么我在这里得到丢了，她说从循环起点算起是k个节点是正确的。

In order to find the start of the loop, the author says that: Since K = mod(k, LOOP_SIZE), we can say that k = K + M * LOOP_SIZE (for any integer M), then here is where I get lost, she says that it is correct to say that it is k nodes from the loop start.

我知道碰撞点是从循环起点算起的K个节点，但是为什么也有k个节点？她如何发现K = k？

I understand that the collision point is K nodes from the loop start, but why it is also k nodes? How does she finds that K = k?

推荐答案

好 K 是内部的节点数循环越快的那一个跳跃通过，直到越慢的一个进入循环。较快的一个要比较慢的一个快2倍，因此较快的一个必须总共跳过 2 * k 个节点（因为较慢的一个需要 k 循环）。因此，它在循环中执行的跳转次数为 K = 2 * kk （所有跳转减去到达循环后的跳转次数），因此 K == k

Well K is the number of nodes inside the loop the faster one "jumped" through until the slower one entered the loop. The faster one goes 2x faster than the slower one, so the faster one had to jump through 2*k nodes in total (because it takes k for the slower one to get to the loop). So the number of jumps it did in the loop is K=2*k-k (all jumps minus jumps it made to get to the loop) so K == k

这篇关于野兔和乌龟算法。为什么冲突点和链表头在循环开始时位于相同距离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！