detecting the start of a loop in a singly linked link list?

Question

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?

Answer 1

Step1: Proceed in the usual way, you will use to find the loop, i.e. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps you make and when they both meet again, the count will give you the length of the loop (this is same as counting the number of elements in a circular link list).

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it will be the start of the loop (this is same as finding the n^th element from the end of the link list).

Answer 2

MATHEMATICAL PROOF + THE SOLUTION

Let 'k' be the number of steps from HEADER to BEGINLOOP. Let 'm' be the number of steps from HEADER to MEETPOINT. Let 'n' be the number of steps in the loop. Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P. 

SIMPLE CASE: When k < N

When pointer 'P' would be at BEGINLOOP (i.e. it would have traveled 'k' steps), Q would have traveled '2k' steps. So, effectively, Q is ahead of '2k-k = k' steps from P when P enters the loop, and hence, Q is 'n-k' steps behind the BEGINLOOP now.

When P would have moved from BEGINLOOP to MEETPONT, it would have traveled 'm-k' steps. In that time, Q would have traveled '2(m-k)' steps. But, since they met, and Q started 'n-k' steps behind the BEGINLOOP, so, effectively, '2(m-k) - (n-k)' should be equal to '(m-k)' So,

=> 2m - 2k - n + k = m - k => 2m - n = m => n = m 

THAT MEANS, P and Q meet at the point equal to the number of steps (or multiple to be general, see the case mentioned below) in the loop. Now, at the MEETPOINT, both P and Q are 'n-(m-k)' steps behind, i.e, 'k' steps behind ,as we saw n=m. So, if we start P from HEADER again, and Q from the MEETPOINT but this time with the pace equal to P, P and Q will now be meeting at BEGINLOOP only.

GENERAL CASE: Say, k = nX + Y, Y < n (Hence, k%n = Y)

When pointer 'P' would be at BEGINLOOP (i.e. it would have traveled 'k' steps), Q would have traveled '2k' steps. So, effectively, Q is ahead of '2k-k = k' steps from P when P enters the loop. But, please note 'k' is greater than 'n', which means Q would have made multiple rounds of the loop. So, effectively, Q is 'n-(k%n)' steps behind the BEGINLOOP now.

When P would have moved from BEGINLOOP to MEETPOINT, it would have traveled 'm-k' steps. (Hence, effectively, MEETPOINT would be at '(m-k)%n' steps ahead of BEGINLOOP now.) In that time, Q would have traveled '2(m-k)' steps. But, since they met, and Q started 'n-(k%n)' steps behind the BEGINLOOP, so, effectively, new position of Q (which is '(2(m-k) - (n-k/%n))%n' from BEGINLOOP) should be equal to the new position of P (which is '(m-k)%n' from BEGIN LOOP).

So,

=> (2(m - k) - (n - k%n))%n = (m - k)%n => (2(m - k) - (n - k%n))%n = m%n - k%n => (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y) => 2m%n - 2k%n - n%n + Y%n = m%n - Y => 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n) => m%n = 0 => 'm' should be multiple of 'n'