3

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?

Community
  • 1
  • 1
user2441441
  • 1,237
  • 4
  • 24
  • 45

1 Answers1

2

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.

M. Shaw
  • 1,742
  • 11
  • 15
  • Above, how is S = x * L – user2441441 Jul 24 '15 at 00:27
  • 1
    @user2441441 because for the two nodes to meet first both pointer need to get to the loop and the fast pointer needs have travelled an integer multiple of the loop's size for the both pointers to be at the same node. `F = 2 * S` is given as the faster pointer travels double the nodes of the slower one. `F = S + x * L` is the point i mentioned about the `F - S` being an integer multiple of the loop's size. – M. Shaw Jul 24 '15 at 01:24
  • Ok. I didn't understand (2)How is the fast pointer guaranteed to meet the slow pointer at the head of loop after slow pointer is moved to the head? – user2441441 Jul 24 '15 at 04:53
  • 1
    @user2441441 I have no idea what (2) means, but as I said if you move `N-L` nodes after the two pointers meet you will arrive at the head of the loop (which is the first node reached from the beginning that is within the loop). – M. Shaw Jul 24 '15 at 06:09