Floyd 算法 - 循环检测 - 不终止的例子

Question

有人可以用这个例子解释弗洛伊德算法吗？它对我来说没有终止，算法实现是否完整？。

我的代码有问题吗？代码如下：

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

画得不好请见谅！

Answer 1

你的第二个循环是问题所在。当你退出第一个循环时，slowptr 和 fastptr 都指向 12。然后你将 slowptr 重置为 10，并进入第二个循环。

在第二个循环中，slowptr 和 fastptr 在 10 和 14 之间交替，并且永远不会相同。这就是循环永远不会结束的原因。

Answer 2

您的方法的问题是您退出第一个 while 循环 太早了。如the algorithm states，兔子跳2次，乌龟跳1次，只跳了次，就可以查了。所以算法应该是：

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

参见 an online demo (I agree this is not nice C++ code, but only for demonstration). A cleaner version can be found here。

Floyd 算法 - 循环检测 - 不终止的例子

Floyd algorithm - Cycle Detection - not terminating for the example

c++

algorithm

linked-list

cycle

floyd-cycle-finding