Detecting a loop in a linked list - When would the pointers meet? How is the head of the loop found by intersection?

Question

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

I have understood the solution but I didn't understand two statements I read in some book-

1. If L is the length of the loop, n is the number of nodes,the slow and fast pointers will meet at n x L length - Is this correct? If not, when would they meet? Can someone please explain it in simple terms.

2. To find the head of the loop, after the slow pointer and fast pointer meet, we move the slow pointer to the head and move both the pointers by 1 node until they intersect at the head of the loop - How does moving the slow pointer to the head and then moving both pointers by 1 node make them meet at the starting of the loop?

Answer 1

Before you reach the loop from the start you will need to traverse N - L nodes. (Where N is the total number of nodes except the initial node)

Let S and F be the number of nodes the slow and fast pointers traversed respectively.

For the two nodes to meet, 2 * S = F = S + x * L where x is an integer. Thus S would be L * ceiling( N / L ).

From the end if you move N - L nodes you will reach the start of the loop.