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 ループをすぐに終了することです。アルゴリズムが述べているように、ウサギは 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
    //...
}

オンライン デモを参照してください(これは適切な C++ コードではなく、デモンストレーション用であることには同意します)。よりクリーンなバージョンはここにあります。

于 2015-05-09T15:06:39.793 に答える
0

2 番目のループが問題です。最初のループを終了すると、slowptr と fastptr の両方が 12 を指します。次に、slowptr を 10 にリセットし、2 番目のループに入ります。

2 番目のループでは、slowptr と fastptr が 10 と 14 の間で交互に繰り返され、同じになることはありません。ループが終わらないのはそのためです。

于 2015-05-09T15:03:28.050 に答える