Doubts on finding circular list algorithm

Question

I have the following code in C that tries to find if a list is cyclic or not:

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

I have some questions regarding some parts of it. Fristly, in the first time we enter the while loop, aren't we always going to reach the condition (faster == slower)? We have initialized both faster and slower to point to the same where it points head.

And secondly, why do we want to compare also if (faster->next == slower), don't we have enough with just faster == slower?

Is it working? It looks like you need to remove `faster == slower || ` — zch, Feb 13 '13 at 18:42
Is your question just "how does this algorithm *work*" in general? — WhozCraig, Feb 13 '13 at 19:25
No, WhozCraig is about why the implementation is like this. I copied it from the book Programming Interviews Exposed and I fail to see why is implemented like that. — Hommer Smith, Feb 13 '13 at 19:49
@HommerSmith It is wrong. The right algorithm advances the fast pointer and tail pointer *first* (the fast pointer twice), then checks for end-of-list (fast | fast->next are NULL) or (fast|fast->next) equality against slow, breaking if either are equal. So if your question is whether the book is correct, it is *not*. If you want the right algorithm I'll post it. — WhozCraig, Feb 13 '13 at 20:05
Reading here http://stackoverflow.com/a/6483030/694576 and here http://stackoverflow.com/a/34255/694576 might help getting enlighted. — alk, Feb 15 '13 at 07:20

score 0 · Answer 1 · answered Feb 13 '13 at 18:58

0

Don't start both faster and slower from head. Do error checking and start faster from head->next.

The algo should work without faster->next ==slower.

answered Feb 13 '13 at 18:58

dejavu

3,236
7
35
60

score 0 · Answer 2 · answered Apr 10 '14 at 21:27

The code as printed in the book is, in fact, incorrect and will return 1 except if a null or 1 element list is passed. The errata shows a corrected version.

The fix is to track if this is the first time through the loop, and perform the circular list check starting with the second time through:

 int first = 1;  /* New code */
 while (1) {
     if (!faster || !faster->next)
         return 0;
     else if ((faster == slower || faster->next == slower) && !first)  /* New code */
         return 1;
     else {
         slower = slower->next;
         faster = faster->next->next;
         first = 0; /* New code */
     }
 }

(The code above uses "faster" and "slower" like in your version; the book and errata use "fast" and "slow".)

Doubts on finding circular list algorithm

2 Answers2