CareerCup

take to pointer *a and *b.
1. start the pointers from head.
2. Move one pointer to one step and other to two step forward
3. when both meets at some point, it concludes that there is loop in the list...

the linked list must be end at the loop start point?
Is it looks like "6"?

Assuming the list to be singly linked list, after finding the list to be looped as suggested by Mr.scorpion, we keep a pointer in the loop and start another pointer at the start of the list, we keep incrementing the pointer and keep rotating the another pointer which should be pointed to the pointer in the loop by exactly one circle, if we hit the pointer which is walking through the list we found the starting point of the list.

1. Start with 2 pointers at head
2. Move pointer A one node at a time, move pointer B one node at a time
3. If there is a loop, eventually they will meet.
To find the node where the loop starts:
4. After A and B meet, move A back to head.
5. Move both A and B 1 node at a time. They meet at the node where the loop starts.

To find the point where the loop starts - Two nodes pointing to the same 'next' node is the node from where the loop starts. So Start from any node and add the dest node id to a hashSet. Everytime before u add check if the destination node id is already present in the hashset.

Correction - 'Start from any node' will not work. You have to start from the head of the list

yes @kurskk141....it may be like a 6...... it may be like a '0' also.

Detection of the loop:
-------------------------------
Start with two pointers(Fast and slow) at the head.
Fast will move forward fastly(Two nodes at a time)
Slow will move forward slowly(one node at a time)
Slow == Fast => there is a loop in the linked list.

Loop start point:
-------------------------
Let p1 be the node where Fast and Slow are meeting.
Set p2 = p1.

Advance p2 and wait till p2 == p1, Keep on counting the nodes in between. At the end of this we would have the number of nodes(say count) inside the loop.

Now set temp1 = temp2 =head;
move temp2 till count (Number of nodes in the loop)
Now start moving both the pointers (one node at a time)
when temp1 == temp2 (This is the start of the loop)

every thing is clear except the the algo for finding the starting pt of the loop...please someone explain in clear way..

But how can there be Head in a circular linked list ? I am not getting it .Please explain someone by diagrammatically or by some other means.Thanks

Below code find the loop in O(n) time with the starting point of the loop

/ *
  *  Algorithm
  * Set node value to INT_MIN as an indicator that node is visited
  *  
  * Recursive go to next node until node is NULL or Node value is INT_MIN
  * IF node is NULL then there is no loop
  * IF Node value is INT_MIN then node is previously visited and 
  * the current node is the starting point of loop  
  *
  * While returning reset the node value so that Link List shouldn't alter
*/

struct node {
	int value;
	struct node *next;
};
typedef struct node * Linklist;


//If there is loop in link list return 0 else return 1
int findLoopInLL(Linklist head, Linklist * start)
{
	int result,value;
	if(head)
	{
		if(head->value == INT_MIN)
		{
			*start = head;
			return 0;
		}
		value = head->value;
		head->value = INT_MIN;
		result = findLoopInLL(head->next, start);
		head->value = value;
		return result;
	}
	start = NULL;
	return 1;
}