Clever Geek Handbook

Detecting a loop in a linked list - When will pointers be encountered? How is the head of the loop found by the intersection?

This question is related to: How to define a loop in a linked list?

I figured out the solution, but I didn't understand two statements that I read in some book -

  • If L is the length of the loop, n is the number of nodes, slow and fast pointers will occur at nx L length - is that correct? If not, when did they meet? Can someone explain this in simple terms.

  • To find the head of the loop, after encountering a slow pointer and a fast pointer, we move the slow pointer to the head and move both pointers by 1 node until they intersect at the beginning of the loop - How to move the slow pointer to the head and then move both pointers at 1 node make them meet when starting a loop?

+3


source to share


1 answer


Before you reach the loop from the beginning, you will need to cross the nodes N - L

. (Where N is the total number of nodes other than the starting node)

Let S

and F

be the number of nodes to which slow and fast pointers go.



To satisfy two nodes 2 * S = F = S + x * L

, where x

is an integer. So it S

will be L * ceiling( N / L )

.

From the end, if you move the nodes N - L

, you will reach the beginning of the cycle.

+2


source






More articles:


All Articles