c++ - 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

您的方法存在的问题是您过早退出第一个 while 循环。作为the algorithm states ，兔子跳两次，乌龟跳一次，只有跳完这些，你才能检查。所以算法应该是:

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 (我同意这不是很好的 C++ 代码，但仅用于演示)。可以找到更清洁的版本 here .