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.

  1. typedef struct node
  2. {
  3.   void *data;
  4.   struct node *next;
  5. }mynode;
  6.  
  7. mynode * find_loop(NODE * head)
  8. {
  9.   mynode *current = head;
  10.  
  11.   while(current->next != NULL)
  12.   {
  13.     mynode *temp = head;
  14.     while(temp->next != NULL && temp != current)
  15.     {
  16.       if(current->next == temp)
  17.       {
  18.         printf("\nFound a loop.");
  19.         return current;
  20.       }
  21.       temp = temp->next;
  22.     }
  23.     current = current->next;
  24.   }
  25.   return NULL;
  26. }

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
  1. p=head;
  2. q=head->next;
  3.  
  4. while(p!=NULL && q!=NULL)
  5. {
  6.   if(p==q)
  7.   {
  8.     //Loop detected!
  9.     exit(0);
  10.   }
  11.   p=p->next;
  12.   q=(q->next)?(q->next->next):q->next;
  13. }
  14.  
  15. // 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!