Thursday, January 10, 2013

Simple C Program to Find Loop in the Linked List

This is a famous question asked in many interviews . And you probably know the answer . The Idea to solve this problem is to use two pointers, where one pointers moves by one pointer and another pointer moves by two pointers . The general idea is if two people are running in  a circle if one person is running at 1x speed and another one is running at 2x speed they will meet after 2 rounds(person who is running at 1x speed will complete one round where other one completes 2 rounds ).

Code : (in C)
int detect_loop(struct node * head)
{
if(head==null && head->link==null)
return 0;
struct node* first,second;
first=head;
second=head->link;
while(first!=second)
{
first=first->link;
if(second->link==null || second->link->link==null)
return 0;
second=second->link->link;
}
if(first==second) // found the loop
return 1;
return 0;
}

if the function returns 0 that means there is no loop , otherwise there is a loop in the linked list .

please let me know if there is any bug in the above code.

1 comment:

Unknown said...

If you want to find the node where loop starts, following code does that
if(loop_found){
/* We have detected a loop */
/*Let's count the number of nodes in this loop node */

ptr1 = fast;
while(ptr1 && ptr1->next != slow){
ptr1 = ptr1->next;
k++;
}
/* Now move the other pointer by K nodes */
ptr2 = head;

ptr1 = head;
for(i=0; inext;
}

/* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */

while(ptr1 != ptr2){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

return ptr1->data;
}

Refer to
Detecting loop in singly linked list for analysis and overall algorithms.