弗洛伊德算法 - 週期檢測 - 沒有終止的例子

]![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

弗洛伊德算法 - 週期檢測 - 沒有終止的例子

回答

相關問題