Why is the meeting point in a loop same number of steps as the start of the linked list?

Question

There is this apparently standard approach to find if a linked list has a cycle and then return the node that is at the start of the cycle which is floy's algorithm with slow/fast pointers.
The code and the logic is clear except 1 thing.
The approach is based on the assumption that the node in the loop that the pointers will meet is exactly the same number of steps as from the head of the list till the start of the loop. That part is what I don't get.
So if Slow and Fast both start at the head of the list, when Slow does k steps and reaches the start of the loop, Fast will have done 2k steps and is effectively k steps into the loop.
So fast is ahead of slow by k steps and behind of slow (which is at the start of the loop) N - k where N is the loop size.
Since at each step fast approaches slow and fast is behind slow by N - k nodes, fast will reach slow in N - k steps.
At this point, slow would have done N - k steps and will be in node N - k.
Fast would have done 2(N - k) steps and will be at node 2N - 2k + k = 2N - k (since fast was at node k).
Since this is a loop 2N - k = N - k and hence they meet at node N - k.
But why is N - k node k steps from the start of the loop?
What am I misunderstanding here?

Answer 1

Here is what you are missing.

Whenever both pointers are in the loop and the fast pointer is a multiple of the loop length ahead, the fast pointer has lapped the slow an integer number of times and they are in the same place. If you continued they would separate and will lap again. And again. And again.

The whole reason why the algorithm works is this lapping behavior.

The first time that they meet, it might be at a strict multiple of the cycle length. For example if you have a chain of 24 nodes leading into a cycle of length 7 then they will first meet after 28 steps.

EDIT I was explaining how the cycle detection worked, and not how the detection of the head worked. Here is an alternate explanation of that. In different words.

Suppose we have a chain of i nodes leading to a loop of length j. We initially run fast+slow pointers and they meet. In order to meet, the fast has to have gone some integer number of times more around the loop than the slow one did. So they meet after k*j steps.

At this point the slow pointer traveled k*j steps total, of which i steps were getting to the loop, so it has traveled k*j-i steps inside of the loop.

Now we put the fast pointer at the start, and advance them at the same rate. In another i steps the pointer at the start has reached the loop. The slow pointer, meanwhile, had previously traveled k*j-i steps inside of the loop, and now travelled another i steps for k*j steps inside of the loop. Since k*j is a multiple of the loop length, it is also back at the beginning and they meet again.

Answer 2

Let me give you another way to look at for this problem , and in the end, you might get your answer too.

Variables used for explanation:

• N - total number of node links in linkedlist .
• C - distance from head to the start point of loop
• Y - distance from the starting of loop to the meeting point.
• K - distance from the meeting point to the start of the loop.

So, we can drive some conclusions from these variables.

1. N = C + Y + K
2. Distance covered by slow pointer - Ds = C + Y
3. Distance covered by fast pointer - Df = N + Y

Here ,

• N = 12
• C = 2
• Both Pointers will meet at node number 11, so Y = 8
• K = 2

Since we know that fast pointer is 2 times faster than slow pointer, so Df = 2 * Ds

Using the relation between Df and Ds , and putting there values from above

N + Y = 2 * ( C + Y )

N + Y = 2*C + 2*Y

N = 2*C + Y

Using N's another relation ,

C + Y + K = 2*C + Y

K = C

This concludes that the distance between head and starting of loop equals to the distance between meeting point node and starting of the loop .

Try to understand this and always try to simplify the task by breaking it into smaller chunks .

Hope this will help.

Keep asking , keep growing :)