Floyd algorithm - Cycle Detection - not terminating for the example

Question

]![linked list Can someone please explain Floyd algorithm with this example. It is not terminating for me and is the algorithm implemented complete ?.

Is something wrong with my code? Code is as follows:

Node* FindLoopBegin(Node *head){
 Node *slowptr = head,*fastptr = head;
 bool LoopExists = false;
 while(slowptr && fastptr){
 fastptr = fastptr->next;
 if(fastptr == slowptr) {LoopExists = true;break;}
 if(fastptr == NULL) {LoopExists = false; return NULL;}
 fastptr = fastptr->next;
 if(fastptr == slowptr) {LoopExists = true;break;}
 slowptr = slowptr->next;
 }
 if(LoopExists) {
 slowptr = head;
 while(slowptr != fastptr){
 slowptr = slowptr->next;
 fastptr = fastptr->next;
 }
 return slowptr;
 } 
 return NULL;
}

Apologies for the bad drawing!

• willeM_ Van Onsem: I think you exit the first while loop to fast if you have found a match. The hare should always hop two times.

Answer 1

The problem with your approach is that you exit the first while loop too soon. As the algorithm states, the hare hops two times whereas the tortoise hops one time, only after these hops, you can check. So the algorithm should read:

while(slowptr && fastptr){
 fastptr = fastptr->next;
 //if(fastptr == slowptr) {LoopExists = true;break;} //remove the if loop
 if(fastptr == NULL) {LoopExists = false; return NULL;}
 fastptr = fastptr->next;
 slowptr = slowptr->next;
 //move the if loop down
 if(fastptr == slowptr) {LoopExists = true;break;}
}

You can do a NULL check before the equality check as well:

while(slowptr && fastptr){
 fastptr = fastptr->next;
 //if(fastptr == slowptr) {LoopExists = true;break;} //remove the if loop
 if(fastptr == NULL) {LoopExists = false; return NULL;}
 fastptr = fastptr->next;
 slowptr = slowptr->next;
 //move the if loop down
 if(fastptr && slowptr && fastptr == slowptr) {LoopExists = true;break;}
}

Or a cleaner version:

do {
 fastptr = fastptr->next;
 if(fastptr == NULL) {return NULL;}
 fastptr = fastptr->next;
 slowptr = slowptr->next;
} while(slowptr && fastptr && slowptr != fastptr);
if(slowptr && fastptr && slowptr == fastptr) { //loopexists
 //...
}

See an online demo (I agree this is not nice C++ code, but only for demonstration). A cleaner version can be found here.

• Vishnu: the first loop is broken only when slowptr and fastptr are same right ? even according to your algorithm , the second loop never terminates right ?
• willeM_ Van Onsem: Well, as said already two times (in the answer as well), you should only check after the two hops for the hare and the one hop for the tortoise. Your algorithm does these checks at every update. That's why I've put the if in comment.
• Vishnu: one small doubt - the slowptr must be incremented before the if(fastptr && slowptr && fastptr == slowptr) or after that ? Before the check, fastptr must be two times ahead the slowptr right ? so slowptr must be moved after the if condition?
• willeM_ Van Onsem: No, the if must be evaluated after the slow pointer hopped. So as stated in the code. If you look at the wiki page, you do the check in the while loop. Since you use the while loop to do null checks, you can resolve it by putting the condition in an if loop at the bottom.

Answer 2

Your second loop is the problem. When you exit the first loop both slowptr and fastptr point to 12. Then you reset slowptr to 10, and enter the second loop.

In the second loop, slowptr and fastptr alternate between 10 and 14, and are never the same. That's why the loop never ends.