弗洛伊德算法 - 周期检测 - 没有终止的例子

]![linked list 有人可以请解释Floyd算法与这个例子。它不是终止我的，算法是否实现了完整？弗洛伊德算法 - 周期检测 - 没有终止的例子

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

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

对不良绘图道歉！

来源

2015-05-09 Vishnu

我觉得如果你找到了一个匹配，你可以退出第一个'while'循环来加快速度。野兔应该总是跳两次。 –

与您的方法的问题是，您过早退出第一个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。

来源

2015-05-09 15:06:39

只有当slowptr和fastptr相同时，第一个循环才会被破坏？即使根据你的算法，第二个循环永远不会终止？ – Vishnu

那么，正如已经说过的两次（在答案中），你应该只**在兔子的两跳以及乌龟的一跳之后检查。您的算法会在每次更新时执行这些检查。这就是为什么我把“if”置于评论中。 –

有一点疑问 - slowptr必须在if（fastptr && slowptr && fastptr == slowptr）之前或之后递增？在检查之前，fastptr必须比slowptr快两倍？所以slowptr必须在if条件后移动？ – Vishnu

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

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

来源

2015-05-09 15:03:28 zmbq

弗洛伊德算法 - 周期检测 - 没有终止的例子

回答

相关问题