3

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

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

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

画的不好请见谅！

4

2 回答 2

3

您的方法的问题是您过早退出第一个 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++ 代码，但仅用于演示）。可以在这里找到更简洁的版本。

于 2015-05-09T15:06:39.793 回答
0

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

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

于 2015-05-09T15:03:28.050 回答