Finding a circular loop in a linked list

August 29th, 2009  |  Published in Amit Sahrawat, Data Structures








There are several ways to find out if a loop is present in the linked list or not. Let’s look at the two ways:

1) If we can modify the linked list structure, then insert a Boolen (bool) flag called visited in the structure.

Start traversing the linked list, on every node mark the flag visit ‘true’.
If the flag for a particular node is already ‘true’ that means the node has already been visited i.e. there is
a loop in the list ‘break’ from the traverse loop.
Else if you reach the end (list->next == NULL) without encountering any node with visit flag true,
signifying the absence of a loop in the list.

2) Without modifying the structure,

Take an extra pointer in the traversing function, make it point to the next node, and make it jump to
every second node and compare the two nodes.(i.e. one pointer will move forward normally while the
other will move faster, twice as the original)
If there is loop in the node, the two pointers will point at some time at the address value, break at that
point.
Otherwise there is no loop in the list.
Bool IsLoop(struct list* node)
{
          Struct list* temp = NULL;
          Temp = node->next;
          while((node->next != NULL) && (temp->next != NULL))
          {
               If(temp == NULL)
                              Return true;
               Else{
                           Node = node -> next;
                           Temp = temp->next->next;
               }                    
          }
          return false;
}

Subscribe

Get articles in your inbox.

Enter your email address:

Join Us

Twitter Chatter


Recommendations

Archives

Categories