How would you detect a loop in a linked list? Write a C program to detect a loop in a 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;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s