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!
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.