1

リンクリストが与えられた場合、それが非循環であるかどうかを調べたい場合は、異なる速度でリストを実行する2つのポインターを持つことができることを理解しています。次に、速いものと遅いものの値を比較し、両方が同じである場合、リストは循環的であることがわかります。しかし、私は人々が遅いポインターを次の速いポインターと比較しているのを見てきました。このコードのように：

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

なぜこの条件が必要なのですか：faster->next == slower?? これだけでは十分ではありません：faster == slower

ありがとう

4

1 に答える 1

1

必要ありません。faster->next == slowerが成立する場合faster == slower、次の反復で成立します。

ただし、最初の反復では2つのポインターが常に等しいため、投稿したコードはまだ正しくありません。正しいコードは次のとおりです。

bool findCircular(Node *head)
{
   Node *slower = head;
   Node *faster = head;
   while(true) {
     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
         return false;
     slower = slower->next;
     faster = faster->next->next;

     //if both pointers are ever equal, it's a circular list
     if (faster == slower)
         return true;
   }
}
于 2013-01-20T21:30:56.097 に答える