To solve this problem let’s define what is unique when we are iterating over a linked list with cycle in it.
If cycle does not exist we would eventually iterate to a null or None node, which doesn’t happen if the a cycle exist in the linked list.
But that is not enough to solve the problem, we must set a stopping point for the iteration otherwise we will end up in an inf loop.
To do that let’s make two pointers, one ahead of another by one node. If a cycle exist the slower one will eventually be caught up with the faster one.
Similarly we can use two pointers to detect a cycle in a linked list. Let’s first break down where they might meet.
A=head B=node cycle starts(target) C=somewhere in the cycle
If we use the same approach in the last problem, where both pointers start at A they will meet at C since the second pointer is twice as fast.
The slower pointer traverled x+y while faster pointer traverled x+y+z+y, and since we know faster pointer is twice as fast: x+y+z+y=2(x+y), meaning x=z.
At this pointer both ponter will be at C, meaning if we start another pointer from the head to traverl to B(x distance), the time it takes for the pointer at C to get to B will be the same(z distance) since we know x=z.
So, start another pointer from the head traverling at the same pase as the pointer at C, we should be able to find the cycle starting node B when they meet.