Sunday, December 2, 2012

How to find if linked list is circular or not?

Any answers?


********************************************

Have 2 pointers .. one is slow and the other is fast (fast pointer moves twice whereas slow pointer moves once) .. if the list is circular both the pointers will meet meet.

bool findCircular(Node *head)
{
Node *slower, * faster;
slower = head;
faster = head;
while(true) {

// if the faster pointer encounters a NULL element
if( !faster || !faster->next)
return false;
//if faster pointer ever equals slower or faster's next
//pointer is ever equal to slow then it's a circular list
else if (faster == slower || faster->next == slower)
return true;
else{
// advance the pointers
slower = slower->next;
faster = faster->next->next;
}
}
}

No comments:

Post a Comment