Home Questions Search Forum Contact Guest Book Polls! Got a Question?
PREV Linked Lists NEXT   (7 / 301)     How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list. This is also one of the classic interview questions There are multiple answers to this problem. Here are a few C programs to attack this problem. Brute force method Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop. typedef struct node {   void *data;   struct node *next; }mynode;   mynode * find_loop(NODE * head) {   mynode *current = head;   while(current->next != NULL)   {     mynode *temp = head;     while(temp->next != NULL && temp != current)     {       if(current->next == temp)       {         printf("\nFound a loop.");         return current;       }       temp = temp->next;     }     current = current->next;   }   return NULL; } Visited flag Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list. Fastest method Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one. Here is some code p=head; q=head->next; while(p!=NULL && q!=NULL) {   if(p==q)   {     //Loop detected!     exit(0);   }   p=p->next;   q=(q->next)?(q->next->next):q->next; } // No loop. The next question is how do you delete/eliminate the loop in a linked list once you detect it? I leave it up to you to do that! PREV COMMENTS                                  INDEX                                  PRINT NEXT Last updated: November 3, 2005 www.cracktheinterview.com - Your destination for the most common IT interview questions, answers, frequently asked interview questions (FAQ), C Programs, C Datastructures for technical interviews conducted by the top IT companies around the world!