単一リンクされたリンク リスト内のループの開始を検出しますか?

Question

を使用してリンクリスト内のループの開始を見つける方法はありますか? ポインタは 2 つまでですか?すべてのノードにアクセスして、そのノードに既知のマークを付けて、最初に既知のノードを報告することはしたくありません。これを行う他の方法はありますか?

Answer 1

まさにこの質問を面接のクイズで聞いたことがあります。

最もエレガントな解決策は次のとおりです。

両方のポインターを最初の要素に置きます (A と B とします)。

次にループを続けます::

• A を次の要素に進める
• A を再度次の要素に進めます
• B を次の要素に進める

ポインタを更新するたびに、A と B が同一かどうかを確認してください。ある時点でポインター A と B が同一である場合、ループが発生します。このアプローチの問題は、ループ内を 2 回移動することになる可能性があることですが、ポインター A では 2 回を超えないことです。

2 つのポインターが指している要素を実際に見つけたい場合は、さらに困難になります。リンクされたリストに従うことを何度も繰り返すつもりがない限り、たった 2 つのポインタでそれを実行するのは不可能だと、私は思い切って言いたいと思います。

より多くのメモリを使用してこれを行う最も効率的な方法は、配列の要素へのポインタを置き、それを並べ替えて、繰り返しを探すことです。

Answer 2

のステップ1：は、通常の方法で進み、あなたはループを見つけるために使用する、すなわち、 二つのポインタを持って、彼らは両方のいつかに会う場合、2つのステップで単一のステップと、他の1つをインクリメント、ループがあります。

のステップ2：の（それがあった1つのポインタをフリーズし、あなたが作る手順をカウントワンステップで他のポインタをインクリメントし、両者が再び会うとき、カウントはあなたにループの長さを与えます。この）円形のリンクリスト内の要素の数を数えると同じである。

のステップ3：は、リンクリストの先頭に両方のポインタをリセットし、ループ時間の長さに一つのポインタをインクリメントした後、第2のポインタを開始。 （これは、リンクリストの最後からN ^番目要素を見つけると同じである）一の段階で両方のポインタを増分し、それらが再び会うとき、それはループの開始になります。

Answer 3

の数学的証明+ SOLUTION の

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

の簡単な場合：場合、K の

ポインタ「P」はBEGINLOOPであろうと（すなわち、それは「K」のステップを移動したであろう）、Q「は2K」のステップを移動したであろう。 Pは、ループに入るときに、効果的に、Qは先Pから '2K-K = K' 工程であり、従って、Qは今BEGINLOOP後ろ 'N-K' のステップである。

PはBEGINLOOPからMEETPONTに移動したであろう場合には、

は、「M-K」のステップを移動したであろう。その時点で、Q 'は、2（M-K）' の手順を移動したであろう。しかし、彼らは出会った、そしてQは、効果的に、BEGINLOOPの後ろに「N-K」の手順を開始し、そのため、 '2（M-K） - （N-k）は' '（M-K）' に等しくなければなりません だから、

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

ステップの数に等しい点で、PとQ出会うを意味するループ内（一般的であること、または複数の、下記の場合を参照）。我々は、Mを見N =よう今、MEETPOINTで、PとQの両方が、後ろに 'K' ステップ、すなわち、後ろ 'N-（M-K）' ステップです。 だから、我々は再びHEADERからPを開始し、Q MEETPOINTからではなく、P、PとQと同じペースでこの時間は今BEGINLOOPで会うことになる場合にのみます。

の一般的な場合：言う、K = nXを+ Y、Y （従って、K％N = Y）

ポインタ「P」はBEGINLOOPであろうと（すなわち、それは「K」のステップを移動したであろう）、Q「は2K」のステップを移動したであろう。 Pは、ループに入るときに、効果的に、Qは先Pから「2K-K = K」工程です。しかし、Qは、ループの複数のラウンドを作ったであろうことを意味する、「K」が「N」よりも大きくなるのでご注意下さい。だから、効果的に、Qは今BEGINLOOPの背後にある 'N-（K％N'）の手順です。

PはBEGINLOOPからMEETPOINTに移動したであろう場合には、

は、「M-K」のステップを移動したであろう。 （したがって、効果的に、MEETPOINTは今前方BEGINLOOPので '（M-K）％N' 手順であろう。）その時点で、Q 'は、2（M-K）' の手順を移動したであろう。しかし、彼らは出会った、そしてQはBEGINLOOPの背後にある 'N-（K％N'）の手順を開始し、そう、であるQの効果、新しい位置（「（2（MK）以来 - ）（NK /％n）が％nをLOOP BEGINから％のN ''）（（MK BEGINLOOPから）である）Pの新たな位置に等しくなければならない'。

だから、

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Answer 4

まず、我々は見つけるためにしようと、任意のループリストの中かどうかがあります。ループが存在するならば、我々はループの出発点を見つけることを試みます。このために我々は二つのポインタ、すなわちslowPtrとfastPtrを使用しています。第一の検出（ループのチェック）において、fastPtrは、一度に2つのステップを移動させるが、slowPtrは一度に1つ前のステップによって移動する。

の

"ここに画像の説明を入力します。

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

これは、リスト内の任意のループがある場合fastPtrポインタが他のものよりも二倍速く実行されているので、彼らは、ポイント（上の画像では点7）で会うことは明らかである。

さて、私たちは、ループの開始点を見つけるの第二の問題に来ています。

と仮定し、それらは、（上記画像で述べたように）ポイント7で満たします。その後、slowPtrはミーティングポイント（点7）で、まだループの外に出ると、リストの先頭に立っている点1の意味はなくfastPtr。彼らは同じ、それがループのポイントを開始している場合今、私たちは、そうでない場合、我々はで一歩先を移動する（ここではfastPtrも一歩ずつ動いている）、私たちは同じポイントを見つけるまで再び比較、両方のポインタ値を比較します。

slowPtr   1   2   3   4
fastPtr   7   8   9   4

これで一つの質問は、それが可能であるか、念頭に置いています。だから、良い数学的な証明があります。

とします：

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

詳細ここの詳細

Answer 5

あなたはループを見つけるために使用する通常の方法で進みます。すなわち。二つのポインタを持って、彼らは両方のいつかに満たしている場合は、2つの段階（fastPointer）でシングルステップ（slowPointer）に1つ、他をインクリメント、ループがあります。

あなたはすでにミーティングポイントは、ループの先頭の前にk個のステップであることに気づいているだろうかもしれませんが。

ここで、kは、リストの非ループ状部分のサイズである。

今ループの先頭にゆっくりと移動します。

タグ衝突点で高速に保ちます

それらの各々は、ループスタート（LOOP-のヘッドは明瞭さを得るためにPICを描画する前に、早くがk個のステップであるリストの先頭から低速）

からKステップであります

これで同じ速度でそれらを移動 - 彼らは、ループの開始時に満たしていなければなりません。

など

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

Answer 6

このは、リンクされたリスト内のループの開始を見つけるためのコードです：

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Answer 7

リンク リスト内のループを検索するには 2 つの方法があります。1.2 つのポインタを使用すると、ループがある場合は 1 つは 1 ステップ進み、もう 1 つは 2 ステップ進みます。ある時点で両方のポインタが同じ値を取得し、null に到達することはありません。しかし、ループがない場合、ポインタは 1 つの点で null に達し、両方のポインタが同じ値を取得することはありません。しかし、このアプローチでは、リンク リストにループがあることはわかりますが、ループが正確にどこから始まるのかはわかりません。これも効率的な方法ではありません。

2. 値が一意になるようにハッシュ関数を使用します。重複を挿入しようとしている場合は、例外を介して挿入する必要があります。次に、各ノードを移動してアドレスをハッシュにプッシュします。ポインタが null に達し、ハッシュからの例外がない場合は、リンク リストにサイクルがないことを意味します。ハッシュから例外が発生した場合は、リスト内にサイクルがあり、それがサイクルの開始元のリンクであることを意味します。

Answer 8

リンクされたリストの各ノードのためのメモリを横断しながらように、昇順に割り当てられるように、

さて、私は一つのポインタを使用して方法を試してみました。私は....いくつかのデータセット内の方法を試しノードのアドレスがループと同様に、ループの最初の要素があり、それは、我々が判断することができますを指しているノードのアドレスより大きくなった場合に、リンクリストの先頭からリンクリスト。

Answer 9

私が見つけた最良の答えはここにありました：
ティアンルンヘ：循環リンクリスト内のループ開始点の検索

• 「m」は HEAD と START_LOOP の間の距離です
• 「L」はループの長さです
• 「d」は MEETING_POINT と START_LOOP の間の距離です

• p1 は V で移動し、p2 は 2*V で移動します

  2 つのポインタが交わるとき:走行距離は = m+ n*L -d = 2*(m+ L -d)

  => これは、(ここでは数学的には証明されていませんが) p1 が HEAD から開始し、p2 が MEETING_POINT から開始し、それらが同じペースで移動すると、@ START_LOOP に達することを意味します。

Answer 10

<のhref = "http://umairsaeed.com/blog/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/" RELを参照してください。 = "nofollowをnoreferrer">総合的な答えは、こののリンクます。

Answer 11

1. ループを見つけるために使用する通常の方法を続行します。つまり。2 つのポインターがあり、1 つは 1 ステップで増加し、もう 1 つは 2 ステップで増加します。両方がいつか出会うと、ループが発生します。

2. ポインターの 1 つを固定したままにして、ループ内のノードの総数 (L など) を取得します。

3. ここで、ループ内のこの時点 (ループ内の次のノードへの 2 番目のポインタをインクリメント) から、リンクされたリストを逆にして、通過したノードの数 (たとえば X) を数えます。

4. 次に、ループ内の同じポイントから 2 番目のポインター (ループが壊れている) を使用して、リンクされたリストをたどり、残っているノードの数をカウントします (Y とします)。

5. ループは ((X+Y)-L)\2 ノードの後に​​始まります。または、(((X+Y)-L)\2+1) 番目のノードから開始します。

Answer 12

1. ループを見つけるために使用する通常の方法を続行します。つまり。2 つのポインターがあり、1 つは 1 ステップで増加し、もう 1 つは 2 ステップで増加します。両方がいつか出会うと、ループが発生します。

2. ポインターの 1 つを固定したままにして、ループ内のノードの総数 (L など) を取得します。

3. ここで、ループ内のこの時点 (ループ内の次のノードへの 2 番目のポインタをインクリメント) から、リンクされたリストを逆にして、通過したノードの数 (たとえば X) を数えます。

4. 次に、ループ内の同じポイントから 2 番目のポインター (ループが壊れている) を使用して、リンクされたリストをたどり、残っているノードの数をカウントします (Y とします)。

5. ループは ((X+Y)-L)\2 ノードの後に​​始まります。または、(((X+Y)-L)\2+1) 番目のノードから開始します。

Answer 13

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

Answer 14

1. ループを検出する
2. 各要素のアドレスをセットにコピーします。重複が見つかった場合、それがループの始まりです