38

単一リンクリストが循環/循環であるかどうかを確認するにはどうすればよいですか？検索しようとしましたが、満足のいく解決策が見つかりませんでした。可能であれば、擬似コードまたはJava実装を提供できますか？

例：
1→→→→→→ 、3ここで、2番目は実際にはリストの3番目の要素です。57145755

4

12 に答える 12

78

標準的な答えは、最初に2つのイテレータを取得し、最初のイテレータを1回インクリメントし、2番目のイテレータを2回インクリメントすることです。それらが同じオブジェクトを指しているかどうかを確認してください。次に、2回インクリメントしているものが最初のものに当たるか、最後に到達するまで繰り返します。

このアルゴリズムは、完全な円であるだけでなく、リスト内の循環リンクを検索します。

擬似コード（Javaではなく、テストされていません-頭のてっぺんから）

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
   }
}
于 2009-07-09T12:31:01.340 に答える
16

フロイドのアルゴリズムと呼ばれる単純なアルゴリズムでは、a と b の 2 つのポインターがあり、どちらもリンク リストの最初の要素から始まります。次に、各ステップで a を 1 回、b を 2 回インクリメントします。リストの最後 (ループなし) または a == b (リンクされたリストにループが含まれる) に到達するまで繰り返します。

もう 1 つのアルゴリズムはブレントのアルゴリズムです。

于 2011-02-05T10:31:25.280 に答える
8

私が知っている 3 つの主な戦略:

  1. リストのトラバースを開始し、アクセスしたすべてのノードを追跡します (たとえば、それらのアドレスをマップに保存します)。アクセスする新しいノードごとに、すでにアクセスしたことがあるかどうかを確認してください。すでにノードにアクセスしたことがある場合は、明らかにループがあります。ループがなければ、いずれ終わります。これは、余分な情報を格納するための O(N) スペースの複雑さであるため、あまり良くありません。

  2. カメ/ウサギのソリューション。リストの先頭で 2 つのポインターを開始します。最初のポインターである「亀」は、反復ごとに 1 ノードずつ前進します。もう 1 つのポインターである "Hare" は、反復ごとに 2 つのノードを前方に移動します。ループがない場合、ウサギとカメは両方ともリストの最後に到達します。ループがある場合、うさぎはある時点で亀を追い越します。それが起こると、ループがあることがわかります。これは O(1) 空間の複雑さであり、非常に単純なアルゴリズムです。

  3. アルゴリズムを使用して、リンクされたリストを逆にします。リストにループがある場合、リストを逆にしようとすると、リストの先頭に戻ってしまいます。ループがない場合は、逆に終了して終了します。これは O(1) 空間の複雑さですが、少し醜いアルゴリズムです。

于 2011-02-05T10:32:10.493 に答える
4

私はあなたのノードを数えて、再び頭に着きます。

于 2011-02-05T10:31:17.523 に答える
2

Tortoise-Hareアルゴリズムを使用します。

于 2009-07-09T12:42:18.863 に答える
2

次のアプローチはどうですか：

標準アルゴリズムに従って、リンク リストを昇順に並べ替えます。ソート前：4-2-6-1-5 ソート後：1-2-4-5-6

並べ替えたら、各ノードのデータを確認し、次のようにリンク ノードのデータと比較します。

if(currentcode->data > currentnode->link->data) すなわち循環 = true;

いずれの比較においても、「currentnode->data」のいずれかが、ソートされたリンク リストの「currentcode->link->data」よりも大きい場合、現在のノードが以前のノードを指していることを意味します (つまり、循環)。

みんな、コードをテストするためのセットアップがありません。このコンセプトが機能するかどうかを教えてください。

于 2013-05-03T10:04:44.097 に答える
1

アルゴリズムは次のとおりです。

  1. 最初のノードへのポインターを格納します
  2. 各ノード ポインターをこのポインターと比較してリストをトラバースします。
  3. NULL ポインタに遭遇した場合は、循環的にリンクされていないリストです
  4. トラバース中に最初のノードに遭遇した場合、それは循環的にリンクされたリストです
于 2011-02-05T10:33:58.747 に答える
0

@samozは私の観点から答えを持っています！擬似コードがありません。のようなものになります

yourlistはリンクリストです

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

申し訳ありませんが、コードは非常に疑似的です（最近はJavaよりも多くのスクリプトを実行してください）

于 2009-07-09T12:36:04.273 に答える
0

これは、さまざまなソリューションをコピーできる優れたサイトです。

ループ単一リンクリストを検索

これはそのサイトの勝者です

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

このソリューションは、1967年にRobertW.Floydによって「Non-deterministicAlgorithms」で公開された「Floyd'sCycle-FindingAlgorithm」です。「TheTortoiseandtheHareAlgorithm」とも呼ばれます。

于 2009-07-09T12:42:55.257 に答える
0

1つのノードから開始して記録し、nullポインターまたは開始したノードに到達するまで、リスト全体を繰り返し処理します。

何かのようなもの：

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

これはO（n）であり、単一リンクリストで取得できる最高のものです（間違っている場合は訂正してください）。

または、リスト内のサイクル（中央など）を見つけるには、次のようにします。

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

動的配列の挿入時間のため、これは少し遅くなります。

于 2009-07-09T12:31:00.870 に答える
0

ループから終了することはありません。次のソリューションでも実行できます。

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
      if(i.next()==j)
          break;
    }
}
于 2010-07-15T14:31:20.980 に答える
0

これを試して

/* Link list Node */

struct Node { int データ; struct Node* next; };

/* この関数は、指定されたリンク リストが循環している場合は true を返し、そうでない場合は false を返します。*/ bool isCircular(struct Node *head) { // (head == NULL) return true の場合、空の連結リストは循環します。

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}

于 2016-08-19T10:48:12.597 に答える