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:
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.
Post a Comment