如何找到在给定的链表一个循环的开始节点？让我们称之为周期点

How to find the beginning node of a loop in a given linked list ? Let's call this the cycle point

到目前为止，我已经了解以下（使用快/慢指针）：

So far, I've understand the following (using slow/fast pointer):

在假定列表有大小非循环的一部分 K 在缓慢移动k步 在快速移动2K步 快 - 慢的（2K K）= K 步骤未来 慢是循环的开始;也被称为可圈可点 快（LOOP_LENGTH - K）步骤背后从可圈可点或慢指针在这一点 在每个1步缓慢移动，移动速度快2步和收益慢了1步。 因此，它会采取快速（LOOP_LENGTH - K）的步骤，以满足慢，碰撞 这是一步我不明白： 在此碰撞点，两个节点将是 K 从循环前面的步骤。 一旦碰撞点被发现，移动一个指针链表的头。 现在，在1步/转，直到碰撞的速度移动这两个指针。在他们两个相遇是循环的开始，因此节点的可圈可点 Assume list has a non-looped part of size k slow moves k steps fast moves 2k steps fast is (2k - k)= k steps ahead of slow slow is at the beginning of loop; also known as Cycle point fast is (LOOP_LENGTH - k) steps behind from Cycle point or slow pointer at this point for each 1 step slow moves, fast moves 2 steps and gains on slow by 1 step. Thus, it would take fast (LOOP_LENGTH - k) steps to meet slow and collide This is the step I don't understand: At this collision point, both nodes will be k steps from the front of the loop. Once the collision point is found, move one pointer to the head of list. Now move both pointers at the speed of 1 step / turn till the collide. The node at which they both meet is the beginning of the the loop and hence the Cycle point

有人可以解释我的第9步和之后呢？

Can someone please explain me step 9 and after that ?

感谢

修改

有一件事我想指出的是，在一次循环内，快速将永远不会超过慢指针。他们会发生冲突。这里的原因：慢是我和快速是假设在I-1。当他们移动，缓慢=> 1 + 1和快速将在i + 1的太，因此碰撞。或者，慢是我和快速是在I-2。下一步，慢> I + 1;快：我。下一步，慢> I + 2，快：我+ 2，因此再次碰撞。这么快将永远无法超越缓慢，只在循环内发生碰撞一次！

One thing I'd like to point out is, once inside the loop, fast will never overtake slow pointer. They will collide. Here's why: slow is at i and fast is assuming at i-1. when they move, slow=> i+1 and fast will be at i+1 too, hence collision. OR, slow is at i and fast is at i-2. next move, slow-> i+1; fast: i. next move, slow-> i+2, fast: i+2 and hence collision again. so fast will never be able to overtake slow, only collide once inside the loop!

推荐答案

您6是错的，快速的指针仍然k步距缓慢的指针，它是在当时的周期点;但更好的使用的未来 或的背后的代替的离开的。此外， K 可能会更小，更大，或等于 loop_length 。

Your 6. is wrong, the fast pointer is still k steps away from the slow pointer which is at the cycle point at that time; but better use ahead or behind instead of away. Plus, k may be smaller, bigger, or equal to the loop_length.

所以，快速指针 K 提前一个缓慢的步骤，当这样达到循环点是，在你的假设， K 开始之后的步骤。现在，衡量一个循环，快速指针 K％loop_length 提前循环点的步骤。对？如果 K = some_n * loop_length + R ，快速指针研究步骤提前循环点，这是比方说， R：= K％loop_length 前进步骤。

So, the fast pointer is k steps ahead of a slow one when that's reached the loop point which is, at your supposition, k steps after the start. Now, measuring on a loop, the fast pointer is k % loop_length steps ahead of the loop point. Right? If k = some_n * loop_length + r, the fast pointer is r steps ahead of the loop point, which is to say, r := k % loop_length steps ahead.

但是，这意味着缓慢的指针 loop_length - R的步骤的的提前快1 的，沿循环。这是一个的循环的毕竟。因此， loop_length后 - R的额外的步骤快速指针将捉对缓慢的。每个步骤的指针缓慢移开，快速移动中通过更紧密的两个的步骤。

But that means that the slow pointer is loop_length - r steps ahead of the fast one, along the loop. This is a loop after all. So after loop_length - r additional steps the fast pointer will catch on to the slow one. For each step the slow pointer moves away, the fast moves closer in by two steps.

所以，我们不知道 K ，我们不知道 loop_length 或 - [R ，我们只知道 M = K + loop_length - R = some_n * loop_length + R + loop_length - R =（some_n + 1）* loop_length 。步骤的总数 M ，直到两个指针的交汇点，是环路长度的倍数。

So we don't know k, we don't know loop_length or r, we only know m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length. The total number of steps m until the two pointers' meeting point, is a multiple of the loop length.

所以，现在，我们重新开始，以在开始一个新的指针和慢在那里会见了快速， M 步骤引领新的。我们将新的和相等的速度慢，通过1步在每个时间，并在周期来看，他们应满足 - 因为当新的指针已达到周期来看，二是仍 M 进取的步骤，这是说， M％loop_length == 0 步骤开拓前进的循环。这样，我们找出 K 是（我们算我们的步骤所有的时间），以及周期点。

So now we start over, with a new pointer at the start and the slow where it met the fast, m steps ahead of the new. We move the new and the slow at equal speed, by 1 step at each time, and at the cycle point they shall meet - because when the new pointer has reached the cycle point, the second is still m steps ahead, which is to say, m % loop_length == 0 steps ahead along the loop. That way we find out what k is (we count our steps all the time), and the cycle point.

和我们找到 loop_length 沿环路一个更多的时间去，直到两人见面一次。

And we find loop_length by going along the loop one more time, until the two meet one more time.

又见： http://en.wikipedia.org/wiki/Cycle_detection#Algorithms