Clever Geek Handbook

Floyd's Algorithm - Loop Detection - Doesn't End For Example

]! [linked list Can someone explain Floyd's algorithm in this example. It doesn't end there for me, and the implemented algorithm is complete. "

Is there something wrong with my code? The code looks like this:

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

Sorry for the bad drawing!

+3


source to share


2 answers


The problem with your approach is that you exit the first while loop too early. As the algorithm points out , the hop ridge twice, whereas the hop turtle once, only after these jumps , you can check. Therefore, 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 also do a check NULL

before checking for equality:

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 the online demo (I agree this is not good C ++ code, but just for demonstration). A cleaner version can be found here .

+3


source


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



In the second loop, slowptr and fastptr alternate between 10 and 14 and never match. This is why the cycle never ends.

0


source






More articles:


All Articles