Floyd algorithm - Cycle Detection - not terminating for the example

Question

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!

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.

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.