loops - 単一リンクリストでループの開始を検出しますか？

Question

2つ以下のポインタを使用してリンクリストのループの開始を見つける方法はありますか？ すべてのノードにアクセスして、それを表示済みとしてマークし、最初のノードがすでに表示されていることを報告したくありません。これを行う他の方法はありますか？

Answer 1

ステップ1：通常の方法で続行します。ループを見つけるために使用します。つまり、2つのポインターを用意し、1つをシングルステップで、もう1つを2ステップでインクリメントします。両方がいつか出会う場合は、ループがあります。

ステップ2： 1つのポインターを元の場所でフリーズし、もう1つのポインターを1つのステップでインクリメントして、実行したステップをカウントします。両方が再び出会うと、カウントによってループの長さがわかります（これは、循環リンクリスト）。

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

Answer 2

数学的な証明+ソリューション

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<Nの場合

ポインタ「P」がBEGINLOOPにある場合（つまり、「k」ステップ移動した場合）、Qは「2k」ステップ移動します。したがって、事実上、Pがループに入るときQはPから「2k-k = k」ステップ進んでいます。したがって、QはBEGINLOOPより「nk」ステップ遅れています。

PがBEGINLOOPからMEETPONTに移動した場合、Pは「mk」ステップを移動します。その時、Qは「2（mk）」ステップを移動していました。しかし、彼らが出会い、QがBEGINLOOPの後ろに「nk」ステップを開始したので、事実上、「2（mk）-（nk）」は「（mk）」と等しくなるはずです。

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

つまり、PとQは、ループ内のステップ数（または一般的には複数、以下のケースを参照）に等しいポイントで交わります。ここで、MEETPOINTでは、n = mであるように、PとQの両方が「n-（mk）」ステップ遅れています。つまり、「k」ステップ遅れています。したがって、再びHEADERからPを開始し、MEETPOINTからQを開始すると、今回はPに等しいペースで、PとQはBEGINLOOPでのみ会議になります。

一般的なケース：たとえば、k = nX + Y、Y <n （したがって、k％n = Y）

ポインタ「P」がBEGINLOOPにある場合（つまり、「k」ステップ移動した場合）、Qは「2k」ステップ移動します。したがって、事実上、Pがループに入るとき、QはPから「2k-k=k」ステップより進んでいます。ただし、「k」は「n」よりも大きいことに注意してください。これは、Qがループを複数回実行したことを意味します。したがって、事実上、QはBEGINLOOPよりも'n-（k％n）'ステップ遅れています。

PがBEGINLOOPからMEETPOINTに移動した場合、Pは「mk」ステップを移動します。（したがって、事実上、MEETPOINTはBEGINLOOPよりも'（mk）％n'ステップ進んでいます。）そのとき、Qは' 2（mk）'ステップを移動していました。しかし、彼らが出会い、QがBEGINLOOPの後ろに'n-（k％n）'ステップを開始したので、事実上、Qの新しい位置（つまり'（2（mk）-（nk /％n））％n 'BEGINLOOPからの）は、Pの新しい位置（BEGIN LOOPからの'（mk）％n'）と等しくなければなりません。

それで、

=> (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 3

まず、リストにループがあるかどうかを調べます。ループが存在する場合は、ループの開始点を見つけようとします。このために、slowPtrとfastPtrという2つのポインターを使用します。最初の検出（ループのチェック）では、fastPtrは一度に2ステップ移動しますが、slowPtrは一度に1ステップ進みます。

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

fastPtrポインターは他のポインターより2倍速く実行されているため、リストにループがある場合、それらはポイント（上の画像のポイント7）で出会うことは明らかです。

ここで、ループの開始点を見つけるという2番目の問題が発生します。

仮に、彼らはポイント7で会うと仮定します（上の画像で述べたように）。次に、slowPtrはループから抜け出し、リストの先頭に立ってポイント1になりますが、fastPtrはまだミーティングポイント（ポイント7）にあります。ここで、両方のポインターの値を比較します。同じ場合はループの開始点です。それ以外の場合は、1ステップ先に移動し（ここではfastPtrも毎回1ステップ移動します）、同じポイントが見つかるまで再度比較します。

slowPtr   1   2   3   4
fastPtr   7   8   9   4

ここで、1つの質問が思い浮かびます。それは、どのようにして可能になるのかということです。したがって、優れた数学的証明があります。

仮定する：

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 4

ループを見つけるために使用する通常の方法で続行します。すなわち。2つのポインターがあり、1つはシングルステップ（slowPointer）で、もう1つは2つのステップ（fastPointer）でインクリメントします。両方がいつか出会うと、ループが発生します。

すでにお気づきかもしれませんが、ミーティングポイントはループの先頭の前のkステップです。

ここで、kはリストのループされていない部分のサイズです。

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

衝突点で高速に保つ

それらのそれぞれは、ループの開始からkステップです（リストの最初から遅いですが、ループの先頭の前のkステップが速いです-明確にするために写真を描いてください）

今度はそれらを同じ速度で動かします-それらはループ開始時に会う必要があります

例えば

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

Answer 5

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

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 6

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

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

Answer 7

さて、1つのポインタを使用して方法を試しました...複数のデータセットでこの方法を試しました...リンクリストの各ノードのメモリは昇順で割り当てられるため、リンクリストをトラバースしながらリンクリストの先頭で、ノードのアドレスがそれが指しているノードのアドレスよりも大きくなった場合、ループとループの開始要素があると判断できます。

Answer 8

包括的な回答については、このリンクを参照してください。

Answer 9

私が見つけた最良の答えはここにありました：
tianrunhe：find-loop-starting-point-in-a-circular-linked-list

• '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

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

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 13

1. 1つは高速でもう1つは低速の2つのポインタを取ります。遅いポインターは一度に1つのノードを移動し、速いポインターは一度に2つのノードを移動します。最終的にはそれらが合流し、ループが見つかります。
2. さて、楽しい部分があります。ループをどのように検出しますか？それも簡単です。最初に別の楽しい質問をさせてください。1回のパスでリスト内のノードのnxをどのように検索しますか？簡単な答えは、2つのポインターを取得することです。1つは頭にあり、もう1つは頭のxステップ先にあり、同じ速度でそれらを移動します。2番目のポインターが終わりに達すると、最初のポインターはnxになります。
3. 他の多くの人がこのスレッドで数学的に証明したように、1つのポインターが1つのポインターの2倍の速度で移動する場合、開始からそれらが出会うポイントまでの距離はリストの長さの倍数になります。なぜそうなのか？高速ポインタは低速ポインタの2倍の速度で移動しているため、次のことに同意できます。高速ポインタの移動距離= 2 *（低速ポインタの移動距離）

今：

1. mがサイクルのないループ（ループ内のノード）の長さである場合

2. nがループの実際の長さである場合。

3. xは、スローポインタが作成したサイクル数です。

4. yは、高速ポインターが作成したサイクル数です。

5. そして、Kはループの開始から待ち合わせのポイントまでの距離です

6. このポイントは、ループのサイクル数の後に余分になる両方のポインターのパスの唯一の長さであることに注意してください。したがって、このkの残りの部分は、ループのサイクルと、ヘッドからループの開始までの初期距離です。したがって、両方とも、互いに出会ったサイクルの後、m + n *（作成したサイクル数）+k距離を移動しています。したがって、次のように言うことができます。

   （m + n x + k）= 2（m + n * y + k）

7. これを数学的に解くと、m+kがループの長さの倍数であることがわかります。nie[m+k =（x-2y）* n]

8. したがって、長さの倍数の距離を維持し、最終的に移動すると、ループの開始時に再び会うことになります。なんで？彼らはどこかで会うことができませんか？かなり速いのはすでにkで、遅いのは先頭です。k+ mがnの倍数であるため、両方がmの距離を移動する場合、速いのはループの開始です。ゆっくりとmの距離を移動する場合、mは頭からループの開始までの距離であり、当初はmであると想定していたため、kに一致します。

9. したがって、ループを検出した後、低速ポインタを再びヘッドに設定し、両方を同じ速度で移動させる場合、高速ポインタと低速ポインタの両方が移動しなければならない距離はmになることが数学的に証明されています。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow){
                slow=head;
                while(slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Answer 14

@hrishikeshmishraソリューションに基づくPythonicコードソリューション

def check_loop_index(head):
    if head == None or head.next == None:
        return -1
    
    slow = head.next
    if head.next.next == None:
        return  -1
    fast = head.next.next
    
    # searching for  loops exists or not
    while fast and fast.next:
        if slow==fast:
            break
        slow = slow.next
        fast = fast.next.next
    
    # checking if there is loop 
    if slow != fast:
        return -1
    
    # reseting the slow to head and creating index
    index = 0
    slow = head
    
    # incrementing slow and fast by 1 step and incrmeenting index, if they meet 
    # hen thats the index of node where loop starts
    while slow!=fast:
        slow = slow.next
        fast = fast.next
        index+=1

    return index

Answer 15

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

Answer 16

この正確な質問を面接クイズの質問として聞いたことがあります。

最もエレガントなソリューションは次のとおりです。

最初の要素に両方のポインターを置きます（それらをAおよびBと呼びます）

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

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

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

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

より多くのメモリでそれを行う最も効率的な方法は、要素へのポインタを配列に入れ、それをソートしてから、繰り返しを探すことです。