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


Special Recent Posts

Withdraw Cash from ATM without Card

Withdraw Cash from ATM without Card

September 17th, 2011

Now, there is no need to carry Automated Teller Machine (ATM) card with withdraw cash. Cash-On-Mobi[...]

Health Care For Diabetes

Health Care For Diabetes

September 3rd, 2011

Symptoms to watch out for: If you feel anxious, tired, confused, unusually hungry, or a fast heart b[...]

How To Take Proper Care of Knees

How To Take Proper Care of Knees

August 31st, 2011

Recognize the problem: Firstly, recognize whether it is just a common ache or something more serious[...]

Recommendations

Archives

Categories