finding the beginning node of a loop in a linked list?

Question

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):

1. Assume list has a non-looped part of size k
2. slow moves k steps
3. fast moves 2k steps
4. fast is (2k - k)= k steps ahead of slow
5. slow is at the beginning of loop; also known as Cycle point
6. fast is (LOOP_LENGTH - k) steps behind from Cycle point or slow pointer at this point
7. for each 1 step slow moves, fast moves 2 steps and gains on slow by 1 step.
8. Thus, it would take fast (LOOP_LENGTH - k) steps to meet slow and collide
9. This is the step I don't understand: At this collision point, both nodes will be k steps from the front of the loop.
10. Once the collision point is found, move one pointer to the head of list.
11. 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

Can someone please explain me step 9 and after that ?

Thanks

EDIT:

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!

Answer 1

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.

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.

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.

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.

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.

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

• see also: http://en.wikipedia.org/wiki/Cycle_detection#Algorithms

• brainydexter: can you explain this relationship m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length ?
• Will Ness: I've just substituted the values. :) The total number of steps until the two pointers meet, what is it? We said we have k steps until the cycle point; when slow is at k, fast is r = k % loop_length ahead of the slow; i.e. slow is loop_length - r ahead of the fast - because the slow stands at the cycle point, if we add distances from it to fast, and then from fast towards it, we get loop_length. That's what having a loop means. And r = k % loop_length means k = some_n * loop_length + r for some value some_n (including perhaps 0). So m = k + loop_length - r.
• Will Ness: (contd.) slow is loop_length - r ahead of the fast so it'll take loop_length - r steps for the fast to catch on to the slow, so they will meet, somewhere. And the total number of steps will be m = k + loop_length - r.
• brainydexter: Aha! I think I understand it :) To summarise, fast first travelled (2k:= ) k (non-loop) and is then r steps into loop. At this point, slow is at cycle point and is loop_length - r ahead of fast. Fast will catch up with slow in exactly loop_length - r steps. Hence, m = # of steps for pointers to meet; => m = k + (loop_length - r). This on substitution also yields, some_n factor of loop_length.
• brainydexter: Also, after this its trivial to also find out the length of a linked list which has a loop in it :). I wish I could upvote more !

Answer 2

Hmm.. This kind of problem is tough to explain unless you are talking face to face. I will give it a try.

First of all in step 6: I think the fast pointer should be k distance away from the circle point.

But leave all that. We now have two cars. A fast car at twice the speed the speed of slow car.

Suppose the fast car starts in circular track at k distance away from circle point.

And the slow car starts from the circle point.

Now I am saying that both car will meet at k distance before the circle point.

Why? Because initially the fast car is at k distance from circle point. The fast car will cover n distance when completing the circle first time. Now the fast car is again at k distance from the circle point. But the slow car is at n/2 distance from circle point.

Now the fast car has to cover n-2k distance more to reach k distance before the circle point. And slow car has to cover n/2 - k = (n-2k) / 2 distance to reach k distance before the starting point. Which is exactly half the distance of the path to be covered by the fast car. And fast car is at twice the speed of the slow car.

So obviously they will meet at k distance before from circle point.

• brainydexter: 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!