0

リストが循環的かどうかを確認しようとする C の次のコードがあります。

bool findCircular(Node *head)
{
   Node *slower, * faster;
   slower = head;
   faster = head;
   while(true) {

     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
       return false;
    //if faster pointer ever equals slower or faster's next
    //pointer is ever equal to slow then it's a circular list
     else if (faster == slower || faster->next == slower)
        return true;
     else{
       // advance the pointers
        slower = slower->next;
        faster = faster->next->next;
      }
   }
}

その一部についていくつか質問があります。最初に while ループに入ったとき、常に条件 (速い == 遅い) に到達するのではないでしょうか? 頭を指す同じ場所を指すように、高速と低速の両方を初期化しました。

そして第二に、なぜ (速い->次 == 遅い) の場合も比較したいのfaster == slowerですか?

4

2 に答える 2

0

fasterと の両方を開始slowerしないでくださいhead。エラー チェックを行い、 から開始fasterしhead->nextます。

アルゴリズムは がなくても機能するはずfaster->next ==slowerです。

于 2013-02-13T18:58:17.143 に答える
0

本に印刷されているコードは実際には正しくなく、null または 1 要素リストが渡された場合を除いて 1 を返します。正誤表は修正版を示しています。

修正は、これがループの初回かどうかを追跡し、2 回目から循環リスト チェックを実行することです。

 int first = 1;  /* New code */
 while (1) {
     if (!faster || !faster->next)
         return 0;
     else if ((faster == slower || faster->next == slower) && !first)  /* New code */
         return 1;
     else {
         slower = slower->next;
         faster = faster->next->next;
         first = 0; /* New code */
     }
 }

(上記のコードでは、あなたのバージョンのように「速い」と「遅い」を使用しています。本と正誤表では「速い」と「遅い」を使用しています。)

于 2014-04-10T21:27:36.833 に答える