CareerCup

Algorithm is here :

Take two pointer P and Q;
Move P twice as Q, and move Q one step at once.
start with P = Head = Q;
Q = Q->next;
P = P->next->next; -- check condition of termination(case when no loop)
repeat until P == Q;

Complexity : O(Length of linked list)
Prove is here :
It is easy to see that if the linked list has a loop then after some time both the pointer will be in the loop.
Consider the time when they are in the loop. Now let First pointer is at Ith node, and Second pointer is at Jth node in linked list. Lets assume that node at Ith place is faster one. So Ith node require J-I+1 move in order to reach to Jth node, and we know that First pointer is moving 1 node relative to second one.which mean it move one node nearer to second in every step. so in J-I+1 step's it will reaches to node second. Hence proved.

n* detectloop(n* hptr)
{
	n * slow,*fast;
	slow=fast=hptr;
	do

	{
      slow=slow->next;
      fast=fast->next->next;      
	}while(slow!=fast);
slow=hptr;
while(slow!=fast)
	{
	slow=slow->next;
	fast=fast->next;
	}
	return slow;
}

suppose p and q are the two pointers in that algorithm for finding the loop where p moves one step and q moves two steps....
so the mathematical prove is as follows

p q
1000 1000 (initially both are pointing to same node)
2000 3000
3000 5000
4000 7000
5000 3000(somewhere due to loop it's repeated it's path)
6000 5000
7000 7000(they will meet and say hi to each other) now the loop is detected.)

hence, it's proved that they will meet definitely if loop exists.