Why Floyd’s Tortoise and Hare Algorithm Work? Finding Starting node of a Cycle in a Linked List?

The algorithm instruction said

1. We need to find the 1st intersection point of fast and slow pointer.
2. Now start a new pointer from intersection point and another pointer from the beginning.
3. When they meet each other that will be our cycle starting point.

Let’s see the problem below. We need to find the starting node of the cycle.

Let’s prove it:

After 4 iteration our slow pointer should look like this.

After 4 iteration our fast pointer should look like this.

Now consider before starting cycle we have to go x length. The cycle length is c. And distance from 2 pointer intersection point to cycle starting point is p. Then we can say.

2 * slow pointer travel distance = fast pointer travel distance

Let’s find slow pointer and fast pointer travel distance when intersection each other(red node)

slow pointer travel distance = X+(C-P)

fast pointer travel distance = X + C + (C-P)

we can say

2(X+(C-P)) = X+C+ C -P

2X+2C-2P — X — 2C + P = 0

X — P = 0

X = P

So, it’s prove.