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

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){
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) {
while(slowptr != fastptr){
slowptr = slowptr->next;
fastptr = fastptr->next;
}
return slowptr;
}
return NULL;
}
```

```

+3

source to share

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

All Articles