How can we find the starting node of a loop in link list?

Question

According to the Floyd's cycle finding algorithm, the point where tortoise and hare meets explains the circular nature in the link list.

To find the starting node in the cycle we initialize tortoise pointer to head of the list and starts incrementing hare and tortoise pointer by one unit. The point where they meet denotes the starting node of the cycle.

Please tell me how it works for the given situation.

The link list flows as:

1->2->3->4->5->6->7->8->3

Answer 1

Let's see.

You position the hare and the tortoise at 1, and let them run, the hare twice as fast as the tortoise.

At the zeroth step, both are at 1. At the first step, the tortoise moves to 2 and the hare moves to 3, and so on.

1 1
2 3
3 5
4 7
5 3
6 5
7 7 

So the hare and the tortoise meet at 7.

Now place the tortoise at the beginning, and let them run again, now with the same speed.

1 7
2 8
3 3 

So they indeed have met at the first element of the cycle.

And that's how it works for the given situation.

Answer 2

OK, let's keep it simple.

Say you have two runners A and B. A move forward by 1 node each step, B moves by 2 nodes.

If it's a cyclic list, they will finally meet each other.

At that time

Say the distance A has moved so far is m, so for B it's 2m

Also note that

 m = a + b
2m = a + b + k * lengthOfLoop

Because for B, it has moved whatever distance A has moved, plus k(some number we don't care) of loops. a is the distance before the loop point, b is the distance A moved after the loop point.

Then we have (after some math)

a = k * lengthOfLoop - b

Now we put B back to the head of the list, and reduce his speed to 1.

For B, it's a nodes away from the loop point. For A, he already passed the loop point by b, and according to the equation above, he is also a nodes away from the loop point.

So, after a more steps, A and B will meet again at the loop point.