Алгоритм Флойда — Cycle Detection — не заканчивается для примера

Question

Алгоритм Флойда — Cycle Detection — не заканчивается для примера

]! [связанный список
Может кто-нибудь, пожалуйста, объясните алгоритм Флойда с этим примером. Это не заканчивается для меня, и алгоритм реализован полностью?

Что-то не так с моим кодом? Код выглядит следующим образом:

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

Извиняюсь за плохой рисунок!

3

algorithm c++cycle floyd-cycle-finding linked-list

Решение

Другие решения

Ваш второй цикл — это проблема. Когда вы выходите из первого цикла, slowptr и fastptr указывают на 12. Затем вы сбрасываете slowptr на 10 и входите во второй цикл.

Во втором цикле slowptr и fastptr чередуются между 10 и 14 и никогда не совпадают. Вот почему цикл никогда не заканчивается.

0

Источник

Accepted Answer

Проблема с вашим подходом в том, что вы выйти из первого цикла while слишком рано Как алгоритм утверждает, заяц прыгает два раза, тогда как черепаха прыгает только один раз после этих прыжков, ты можешь проверить. Таким образом, алгоритм должен читать:

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

Вы можете сделать NULL проверить перед проверкой равенства:

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

Или более чистая версия:

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
//...
}

Увидеть онлайн демо (Я согласен, что это не хороший код C ++, но только для демонстрации). Более чистая версия может быть найдена Вот.

3