CareerCup

Using 2 pointers, we can find out if there is a loop by moving the 1st pointer one node at a time and the 2nd one, two nodes at a time, until they meet.
Once they meet, hold on pointer stationary and move the other one node at time, till they meet again - This gives the length of the cycle/loop, say = N.
Now move both the pointers to the start of the linked list/head. Move pointer1 N positions ahead, and then begin to move both pointers one node at a time, till they meet(means keep a distance of N between the 2 pointers). The point where they meet is the start of the cycle.

Sorry the figure got altered accidentally....

1-->2-->3-->4-->5-->6-->7-->8-->3(8th node points to 3rd node - this is the cycle)

nice solution!!

the questions says that you can use only two pointers but for the solution mentioned above. one head pointer and a variable N are used extra.

If we use two+head pointers, and two variables. Then also you could get the starting node of the loop.


1st pointer T1 moves one by one and counts its position n1
one each: 2nd pointer T2 moves from head to T1 and counts its position n2
whenever n1!=n2 break

n2 is the index of the starting pointer and T3 will be the node of the starting pointer

Hi abid,

can you explain it clearly. suddenly where did T3 comes in between?

I know by using two pointers, I am looking for loop detection using only one pointer. ??

I think the total number of iterations to detect looping (including self loop) would be 2n - 1.

1->2->3->4->5->6->4

Let me know what you think

Just move 1st pointer to it's next and the 2nd pointer to it's next->next until the values of the two nodes meet. The place where they meet, keep one pointer there and point the second pointer to the very first node where we started, in the example case: we will meet at 7. So, keep one pointer pointing to 7 and another to 1. Now start shifting one node at a time. The place they meet again is the starting node.

Just move 1st pointer to it's next and the 2nd pointer to it's next->next until the values of the two nodes match. The place where they meet, keep one pointer there and point the second pointer to the very first node where we started, in the example case: we will meet at 7. So, keep one pointer pointing to 7 and another to 1. Now start shifting one node at a time. The place they meet again is the starting node of the loop.