Erkennen Sie den Beginn einer Schleife in einer einzig verknüpften Linkliste?
https://stackoverflow.com/questions/1536944
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es eine Möglichkeit, den Beginn einer Schleife in einer Linkliste mithilfe der Linkliste herauszufinden? Nicht mehr als zwei Zeiger?Ich möchte nicht jeden Knoten besuchen und markieren, der den ersten Knoten gesehen hat, der bereits gesehen wurde. Gibt es eine andere Möglichkeit, dies zu tun?
Lösung
Ich habe diese genaue Frage als Interview -Quizfrage gehört.
Die eleganteste Lösung ist:
Setzen Sie beide Zeiger beim ersten Element (nennen Sie sie A und B)
Dann looping weiter ::
- Fortschreiten Sie A zum nächsten Element
- Fortschreiten Sie A wieder zum nächsten Element
- Fortschreiten B zum nächsten Element
Wenn Sie tatsächlich das Element finden möchten, das zwei Zeiger darauf hinweist, ist das schwieriger. Ich würde aus einem Glied gehen und sagen, dass es mit nur zwei Zeigern unmöglich ist, es sei denn, Sie sind bereit, nach der verlinkten Liste eine große Anzahl von Malen zu wiederholen.
Die effizienteste Art, dies mit mehr Erinnerung zu tun, wäre, die Zeiger auf die Elemente in und Array zu setzen, sie zu sortieren und dann nach einer Wiederholung zu suchen.
Andere Tipps
Schritt 1: Fahren Sie auf die übliche Weise fort, Sie werden die Schleife finden, dh zwei Zeiger, die einen in einen einzigen Schritt und einen anderen in zwei Schritten erhöhen. Wenn beide in irgendwann in einer Zeit treten, gibt es eine Schleife.
Schritt 2: Frieren Sie einen Zeiger ein, wo er war, und erhöhen aufführen).
Schritt 3: Setzen Sie beide Zeiger auf den Beginn der Linkliste zurück, erhöhen Sie einen Zeiger auf die Länge der Schleifenzeiten und starten Sie dann den zweiten Zeiger. Inkrementieren Sie beide Zeiger in einem Schritt und wenn sie sich wieder treffen, wird es der Beginn der Schleife sein (dies ist das gleiche wie das Finden des nth Element vom Ende der Linkliste).
Mathematischer Beweis + die Lösung
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.
Einfacher Fall: Wenn K <n
Wenn Zeiger 'P' an beginloop sein würde (dh er wäre 'k' Schritte gereist), hätte Q '2K' Schritte gereist. Effektiv ist Q vor '2K-K = k' Schritten von P voraus, wenn P in die Schleife eintritt, und daher ist Q 'nk' Schritte hinter dem beginloop jetzt.
Wenn P von Beginnloop zu MeetPont gezogen wäre, wäre es 'Mk' Schritte gereist. In dieser Zeit hätte Q '2 (mk)' Schritte gereist. Aber da sie sich trafen, und Q starteten Schritte hinter dem beginloop, also sollte '2 (mk) - (nk)' gleich '(mk)' so sein.
=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m
Das bedeutet, dass P und Q an dem Punkt entsprechen, der der Anzahl der Schritte (oder mehreren zu allgemeinem, siehe den unten genannten Fall) in der Schleife. Jetzt, am Meetpoint, sind sowohl P als auch Q 'n- (mk)' Schritte hinter sich, dh 'k' Schritte dahinter, wie wir n = m sahen. Wenn wir also wieder P vom Header starten und Q vom Meetpoint aus dem Tempo entspricht P, P und Q nun nur bei Beginnloop.
Allgemeiner Fall: Sag, k = nx + y, y <n(Daher k%n = y)
Wenn Zeiger 'P' an beginloop sein würde (dh er wäre 'k' Schritte gereist), hätte Q '2K' Schritte gereist. Effektiv ist Q vor '2K-K = K' Schritten von P voraus, wenn P in die Schleife eintritt. Bitte beachten Sie jedoch, dass 'k' größer als 'n' ist, was bedeutet, dass Q mehrere Runden der Schleife gemacht hätte. Effektiv ist Q 'n- (k%n)' Schritte hinter dem beginloop jetzt.
Wenn P von Beginnloop zu Meetpoint umgezogen wäre, hätte es 'Mk' Schritte gereist. (Daher wäre Meetpoint effektiv auf '(mk)%n' Stufen vor Beginnloop jetzt.) In dieser Zeit hätte Q '2 (mk)' Schritte gereist. Aber da sie sich trafen, und Q starteten 'n- (k%n)' Schritte hinter dem beginloop, also effektiv neue Position von q (was ist '(2 (mk) - (nk/%n))%n 'von Anfangsloop) sollte gleich der neuen Position von P (was' (mk)%n 'von Anfang Schleife) sein.
So,
=> (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'
Zuerst versuchen wir herauszufinden, gibt es eine Schleife in der Liste oder nicht. Wenn die Schleife existiert, versuchen wir, den Startpunkt der Schleife herauszufinden. Dazu verwenden wir zwei Zeiger, nämlich Slowptr und Fastptr. Bei der ersten Erkennung (Überprüfung nach Schleifen) bewegt FastPTR zwei Schritte gleichzeitig, aber Slowptr bewegt sich sofort um einen Schritt.
slowPtr 1 2 3 4 5 6 7 fastPtr 1 3 5 7 9 5 7
Es ist klar, dass sie sich am Punkt (Punkt 7 im obigen Bild) erfüllen, da der FastPTR -Zeiger zweimal schneller als andere läuft, wenn sie eine Schleife in der Liste haben.
Jetzt kommen wir zum zweiten Problem, einen Startpunkt der Schleife zu finden.
Nehmen wir an, sie treffen sich an Punkt 7 (wie im obigen Bild erwähnt). Dann kommt Slowptr aus der Schleife und steht am Anfang der Liste an Punkt 1, aber Fastptr immer noch am Meeting Point (Punkt 7). Jetzt vergleichen wir beide Zeigerwert, wenn sie gleich sind, dann ist es der Ausgangspunkt der Schleife, sonst bewegen wir uns einen Schritt nach vorne (hier bewegt sich FASTPTR auch jedes Mal um einen Schritt) und vergleichen erneut, bis wir den gleichen Punkt finden.
slowPtr 1 2 3 4 fastPtr 7 8 9 4
Jetzt kommt eine Frage, wie ist es möglich. Es gibt also einen guten mathematischen Beweis.
Vermuten:
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.
Fahren Sie auf die übliche Weise fort, die Sie verwenden, um die Schleife zu finden. dh. Haben Sie zwei Zeiger, erhöhen Sie einen in den einzelnen Schritt (Slowpointer) und einen anderen in zwei Schritten (Fastpointer). Wenn sich beide irgendwann in einer Zeit treffen, gibt es eine Schleife.
Wie Sie vielleicht bereits erkannt hätten, dass ein Treffpunkt K. Schritt vor dem Kopf der Schleife ist.
wobei k Größe des nicht geschlossenen Teils der Liste hat.
Bewegen Sie sich nun langsam zu Kopf der Schleife
Halte schnell am Kollisionspunkt
Jeder von ihnen ist ein K-Schritt aus dem Schleifenstart (langsam von Anfang der Liste, in der so schnell K-Schritt vor dem Kopf des Schleiers ist- zeichnen Sie das Bild, um die Klarheit zu erhalten)
Bewegen Sie sie nun mit gleicher Geschwindigkeit - sie müssen sich beim Start des Schleifens treffen
z.B
slow=head
while (slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
Dies ist Code, um den Start der Schleife in der verknüpften Liste zu finden:
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);
}
Es gibt zwei Möglichkeiten, die Schleifen in einer Linkliste zu finden. 1. Verwenden Sie zwei Zeiger einen Schritt und andere Fortschritte zwei Schritte, wenn es Schleife gibt. In irgendeinem Punkt erhalten beide Zeiger den gleichen Wert und erreichen niemals Null. Aber wenn es keinen Schleifenzeiger gibt, der in einem Punkt null ist und beide Zeiger niemals den gleichen Wert erhalten. Bei diesem Ansatz können wir jedoch eine Schleife in der Linkliste erhalten, aber wir können nicht sagen, wo genau das Starten der Schleife starten. Dies ist auch nicht der effiziente Weg.
- Verwenden Sie eine Hash -Funktion so, dass der Wert eindeutig sein sollte. Wenn wir versuchen, das Duplikat durch die Ausnahme einzufügen. Fahren Sie dann durch jeden Knoten und drücken Sie die Adresse in den Hash. Wenn der Zeiger auf Null reicht und keine Ausnahme vom Hash bedeutet, gibt es keinen Zyklus in der Linkliste. Wenn wir eine Ausnahme von Hash erhalten, bedeutet dies einen Zyklus in der Liste und das ist der Link, aus dem der Zyklus beginnt.
Nun, ich habe einen Weg versucht, indem ich einen Zeiger benutze ... Ich habe die Methode in mehreren Datensätzen ausprobiert ... als Speicher für jeden der Knoten einer verknüpften Liste in einer zunehmenden Reihenfolge. Der Kopf der verknüpften Liste, wenn die Adresse eines Knotens größer wird als die Adresse des Knotens, auf die er zeigt, können wir feststellen, dass es eine Schleife sowie das Anfangselement der Schleife gibt.
Die beste Antwort, die ich gefunden habe, war hier:
Tianrunhe: Find-Loop-Start-Punkt-in-a-kreisförmiger List
- 'M' Abstand zwischen Kopf und Start_loop
- 'L' sein Schleifenlänge
- 'D' Distanz zwischen Meeting_Point und Start_loop sein
P1 bewegt sich bei V und P2 bei 2*V bewegt
Wenn die 2 Zeiger treffen: Entfernung ist = m+ n*l -d = 2*(m+ l -d)
=> Was bedeutet (nicht hier demonstriert), dass, wenn P1 von Head & P2 beginnt
Beziehen auf Dies Link für eine umfassende Antwort.
Fahren Sie auf die übliche Weise fort, die Sie verwenden, um die Schleife zu finden. dh. Haben Sie zwei Zeiger, die einen in einzelnen Schritt und einen anderen in zwei Schritten erhöhen. Wenn beide in irgendwann in einer Zeit treffen, gibt es eine Schleife.
Halten Sie einen der Zeiger fest und erhalten Sie die Gesamtzahl der Knoten in der Schleife sagen L.
Nun ab diesem Zeitpunkt (insteigender zweiter Zeiger auf den nächsten Knoten in der Schleife) in der Schleife in die verknüpfte Liste umkehren und die Anzahl der durchquerten Knoten zählen, z. B. X.
Verwenden Sie nun den zweiten Zeiger (Schleife ist kaputt) aus demselben Punkt in der Schleife, die die verknüpfte Liste verhandelt und die Anzahl der verbleibenden Knoten zählen
Die Schleife beginnt nach den ((x+y) -l) 2-Knoten. Oder beginnt am (((x+y) -l) 2+1).
Fahren Sie auf die übliche Weise fort, die Sie verwenden, um die Schleife zu finden. dh. Haben Sie zwei Zeiger, die einen in einzelnen Schritt und einen anderen in zwei Schritten erhöhen. Wenn beide in irgendwann in einer Zeit treffen, gibt es eine Schleife.
Halten Sie einen der Zeiger fest und erhalten Sie die Gesamtzahl der Knoten in der Schleife sagen L.
Nun ab diesem Zeitpunkt (insteigender zweiter Zeiger auf den nächsten Knoten in der Schleife) in der Schleife in die verknüpfte Liste umkehren und die Anzahl der durchquerten Knoten zählen, z. B. X.
Verwenden Sie nun den zweiten Zeiger (Schleife ist kaputt) aus demselben Punkt in der Schleife, die die verknüpfte Liste verhandelt und die Anzahl der verbleibenden Knoten zählen
Die Schleife beginnt nach den ((x+y) -l) 2-Knoten. Oder beginnt am (((x+y) -l) 2+1).
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);
}
- Schleife erkennen
- Kopieren Sie die Adresse jedes Elements in SET. Wenn ein Duplikat gefunden wird, ist dies der Beginn der Schleife
