CODEWITHSUNDEEP
cpointerslinked-list
Hommer Smith
Hommer Smith

Reputation: 27862

Find if list is acyclic in C using two pointers - Why compare with faster->next?

I understand that, given a linked list, if we want to find if it is acyclic, we can have two pointers that run through the list at different speeds. Then if we compare the values of the faster with the slower and both are the same, we know that the list is cyclic. However, I have seen people also comparing the slower pointer with the next's faster pointer. Like this code:

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;
      }
   }
}

Why is this conditional necessary: faster->next == slower ?? Is not enough with just this: faster == slower

Thanks

Upvotes: 1

Views: 166

Answers (1)

rburny
rburny

Reputation: 1569

It's not needed. If faster->next == slower holds, faster == slower will hold in the next iteration.

However, the code you posted is still incorrect, because two pointers are always equal in the first iteration. Correct code would be:

bool findCircular(Node *head)
{
   Node *slower = head;
   Node *faster = head;
   while(true) {
     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
         return false;
     slower = slower->next;
     faster = faster->next->next;

     //if both pointers are ever equal, it's a circular list
     if (faster == slower)
         return true;
   }
}

Upvotes: 1

Related Questions