66

単一リンクリストにループがあるかどうかをどのように検出できますか?? ループがある場合、ループの開始点、つまりループが開始されたノードを見つける方法。

4

13 に答える 13

133

これは、リストを介して2 つのポインターを実行するだけで検出できます。このプロセスは、同じ名前の寓話にちなみ、カメとウサギのアルゴリズムとして知られています。

  • まず、リストが空 ( headis null) かどうかを確認します。もしそうなら、サイクルは存在しないので、今すぐやめてください。
  • それ以外の場合はtortoise、最初のノードで最初のポインターを開始し、2 番目のノードでhead2 番目のポインターを開始します。harehead.next
  • 次に、 (要素が 1 つのリストでは既に true である可能性があります) になるhareまで連続してループし、反復ごとに1 ずつ、 2 ずつ進みます。うさぎは先に出発し、より速く走るため、(端がある場合)最初に端に到達することが保証されます。nulltortoisehare
  • 終わりがない場合 (つまり、サイクルがある場合)、それらは最終的に同じノードを指し、サイクル内のどこかにノードが見つかったことを認識して停止できます。

で始まる次のループを考えてみましょう3:

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6

tortoise1 と2から始まりhare、次の値を取ります。

(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)

それらは で等しくなり(6,6)、非ループ リストでは常にそれを超えるhare必要があるため、サイクルを発見したことを意味します。tortoise

擬似コードは次のようになります。

def hasLoop (head):
  return false if head = null           # Empty list has no loop.

  tortoise = head                       # tortoise initially first element.
  hare = tortoise.next                  # Set hare to second element.

  while hare != null:                   # Go until hare reaches end.
    return false if hare.next = null    # Check enough left for hare move.
    hare = hare.next.next               # Move hare forward two.

    tortoise = tortoise.next            # Move tortoise forward one.

    return true if hare = tortoise      # Same means loop found.
  endwhile

  return false                          # Loop exit means no loop.
enddef

このアルゴリズムの時間の複雑さはO(n)、(カメとウサギが) 訪問したノードの数がノードの数に比例するためです。

ループ内のノードがわかれば、ループの開始点O(n)を見つける確実な方法もあります。

ループのどこかで要素を見つけたが、ループの開始位置がわからない場合は、元の位置に戻りましょう。

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6
                             \
                              x (where hare and tortoise met).

これは従うべきプロセスです:

  • 進めhareて にセットsizeし1ます。
  • hareそして、とtortoiseが異なる限り、は前進し続け、そのたびhareに増加します。sizeこれにより、最終的にサイクルのサイズが得られます。この場合は 6 です。
  • この時点で が である場合sizeは、すでに1サイクルの開始点にいる必要があります (サイズ 1 のサイクルでは、サイクルに存在できる可能性のあるノードは 1 つしかないため、最初のノードでなければなりません)。この場合、最初に戻って、以下の残りの手順をスキップします。hare
  • それ以外の場合は、 と の両方hareをリストtortoiseの最初のhare要素に設定し、正確なsize回数 (7この場合は まで) 進めます。これにより、サイクルのサイズだけ異なる 2 つのポインターが得られます。
  • hare次に、とが異なる限り、tortoise両方を一緒に進めます (ウサギはより落ち着いたペースで、亀と同じ速度で走っています。最初の走りで疲れているようです)。sizeそれらは常に互いに正確に離れた要素のままであるため、サイクルの開始に戻るのとまったく同時にサイクルの開始にtortoise到達します。hare

次のウォークスルーでそれを確認できます。

size  tortoise  hare  comment
----  --------  ----  -------
   6         1     1  initial state
                   7  advance hare by six
             2     8  1/7 different, so advance both together
             3     3  2/8 different, so advance both together
                      3/3 same, so exit loop

したがって3、 はサイクルの開始点であり、これらの操作 (サイクルの検出とサイクル開始の検出) は両方ともO(n)連続して実行されるため、全体として もO(n)です。

これが機能するというより正式な証拠が必要な場合は、次のリソースを調べることができます。

  • 姉妹サイトに関する質問。
  • ウィキペディアのサイクル検出ページ。また
  • 2016 年 4 月 17 日、Peter Gammie による「The Tortoise and the Hare Algorithm」。

メソッドのサポートが必要なだけの場合 (正式な証明ではありません)、次の Python 3 プログラムを実行して、多数のサイズ (サイクル内の要素の数) とリードイン (プロセスの前の要素) の実行可能性を評価できます。サイクル開始）。

2 つのポインターが交わるポイントが常に検出されることがわかります。

def nextp(p, ld, sz):
    if p == ld + sz:
        return ld
    return p + 1

for size in range(1,1001):
    for lead in range(1001):
        p1 = 0
        p2 = 0
        while True:
            p1 = nextp(p1, lead, size)
            p2 = nextp(nextp(p2, lead, size), lead, size)
            if p1 == p2:
                print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
                break
于 2012-04-23T06:08:03.910 に答える
7

ハッシュ マップを使用して、リンク リストにループがあるかどうかを調べることもできます。以下の関数では、ハッシュ マップを使用して、リンク リストにループがあるかどうかを調べます。

    static bool isListHaveALoopUsingHashMap(Link *headLink) {

        map<Link*, int> tempMap;
        Link * temp;
        temp = headLink;
        while (temp->next != NULL) {
            if (tempMap.find(temp) == tempMap.end()) {
                tempMap[temp] = 1;
            } else {
                return 0;
            }
            temp = temp->next;
        }
        return 1;
    }

時間の複雑さは O(n) であるため、2 つのポインター メソッドが最適なアプローチです。

于 2014-05-11T09:56:11.040 に答える
3

この回答は、Narasimha Karamanchi による Data structure book で読みました。

カメとウサギのアルゴリズムとも呼ばれるフロイド サイクル検出アルゴリズムを使用できます。この場合、2 つのポインターが使用されます。1 つ (たとえば) は 1 つのノードによって進められ、もう 1 つ (たとえば) は 2 つのノードによって進められます。単一のリンクされたリストにループが存在する場合、それらは必ずある時点で一致します。slowPtrfastPtr

struct Node{
int data;
struct Node *next;

}

 // program to find the begin of the loop

 int detectLoopandFindBegin(struct Node *head){
      struct Node *slowPtr = head, *fastPtr = head;
      int loopExists = 0;
      // this  while loop will find if  there exists a loop or not.
      while(slowPtr && fastPtr && fastPtr->next){                                                  
        slowPtr = slowPtr->next;                      
        fastPtr = fastPtr->next->next;
        if(slowPtr == fastPtr)
        loopExists = 1;
        break;
      }

ループが存在する場合は、ポインターの 1 つをヘッドに向けて、両方のポインターを 1 つのノードだけ進めます。それらが出会うノードは、単一のリンクされたリストのループの開始ノードになります。

        if(loopExists){      
             slowPtr = head;
             while(slowPtr != fastPtr){
               fastPtr = fastPtr->next;
               slowPtr = slowPtr->next;
             }
             return slowPtr;
          }
         return NULL;
        }
于 2017-12-19T10:04:15.757 に答える
0

選択した回答を見て、いくつかの例を試してみたところ、
(A1,B1), (A2,B2) ... (AN, BN) がポインター A と B のトラバーサルであることがわかりました。
ここで、A は 1 要素をステップします。 B ステップ 2 要素、Ai と Bj は A と B が通過するノード、AN=BN。
次に、ループが開始するノードは Ak です。ここで、k = floor(N/2) です。

于 2016-11-23T11:35:40.267 に答える
-1

まったく別の方法:- リンクされたリストを逆にします。再び先頭に到達するとリストにループがあり、NULL を取得するとループはありません。総時間計算量は O(n)

于 2016-02-06T05:10:47.200 に答える