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!

I think you exit the first `while` loop to fast if you have found a match. The hare should always hop two times. — Willem Van Onsem, May 09 '15 at 14:59

Willem Van Onsem · Accepted Answer · 2015-05-09T15:34:09.047

3

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.

edited May 09 '15 at 15:34

answered May 09 '15 at 15:06

Willem Van Onsem

443,496
30
428
555

the first loop is broken only when slowptr and fastptr are same right ? even according to your algorithm , the second loop never terminates right ? – Vishnu May 09 '15 at 15:09
1

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. – Willem Van Onsem May 09 '15 at 15:10
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? – Vishnu May 09 '15 at 15:23
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. – Willem Van Onsem May 09 '15 at 15:26

score 0 · Answer 2 · answered May 09 '15 at 15:03

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.

Floyd algorithm - Cycle Detection - not terminating for the example

2 Answers2