0

次の場合にループを検出したい

1-2-3-4-5
|----------| ===> case 1

1-2-3-4-5
|-------|    ===> case 2

ケース1のサイクル検出アルゴリズムは正しく機能しますが、ケース2では機能しません。ケース2のドライランを実行したところ、うさぎポインターが正常に終了することがわかりました。また、ケース2には2つの次のポインターが含まれているため、単一リンクリストは有効ではないと思いました。ケース2の私の仮定は正しいですか？全体のシナリオは、単一リンクリスト用ですか？

4

2 に答える 2

2

ヒープメモリの割り当てを伴わないサイクル検出のソリューションは次のとおりです。

struct Node {
   int val;
   struct node * next;
};

bool containsCycle(Node * head)
{
   Node * walker = head;
   NOde * fastWalker = head;  
   while(walker && fastWalker)
   {
      fastWalker = fastWalker->next;
      if(walker == fastWalker)
         return true;
      if(fastWalker)
        fastWalker = fastWalker->next;
      if(walker == fastWalker)
         return true;
      walker = walker->next;
   }
   // Fell out of the loop, no cycle
   return false;
}

このアルゴリズムは、異なる速度で進む2つのポインターを使用します。リストにサイクルがある場合、2つのポインターはある時点で互いに等しくなります。

于 2012-08-09T04:54:39.687 に答える
1

あなたが求めていることについての一連の仮定に基づいて答えます。

あなたのフォーマットが台無しになり、「next」と呼ばれる1つのポインターを持つノード構造体から構築された単一リンクリストを使用していると思います。

また、ルートと呼ばれるリストの最初の要素へのポインターがあると仮定します。

次に、アルゴリズムは root のコピーを保存し、次にリストを調べて root に戻るかどうかを確認することで構成されていると仮定します。

これは次のような場合に機能します。

A -> B -> C -> D -> E   //and E -> A.

しかし、次の場合は機能しません

A -> B -> C -> D -> E   //and E -> B.

1 つの方法は、構造体に新しいフィールドを追加するか、hashTable を保持することによって、歩きながらアクセスした各ノードをマークし、繰り返し要素を取得するかどうかを確認することです。

(実際には、10 個ごとのノードをハッシュテーブルに追加することもできますが、訪問した各ノードをハッシュテーブルと照合して重複がないか確認してください)。

リンクされたリストにある (そして変更されていない) 要素の数が前もってわかっている場合は、単純にその回数だけ歩き、次のノードが null かどうかを確認します。

于 2012-08-09T04:20:41.890 に答える