Floyd's cycle-finding algorithm proof (Detecting loops in linked lists)

Question

The algorithm uses a fast and a slow pointer to detect a loop in a linked list. My question is, how do I prove that the distance between the point where the two pointers collide in the loop and the start of the loop is equal to the distance between the head of the linked list and the start of the loop?

Answer 1

Consider the speed of the slow pointer as "x" and the speed of the fast as "2x". Using simple relative motion you can prove that these two will eventually meet if there is a loop.
Now, consider the time being same, so the distance traveled by fast pointer is twice as more than the slow.
If slow travels a distance of a+b then fast will travel a+2b+c. The link will provide you a better understanding.
2*(a+b)=a+2b+c
Solving this equation gives you a=c.
This question already has been answered, you may refer to the link below:
https://cs.stackexchange.com/questions/10360/floyds-cycle-detection-algorithm-determining-the-starting-point-of-cycle