Diese Frage mag alt sein, aber mir fiel keine Antwort ein.
Angenommen, es gibt zwei Listen unterschiedlicher Länge, die an einem Punkt zusammengeführt werden . Woher wissen wir, wo der Zusammenführungspunkt liegt?
Bedingungen:
- Wir kennen die Länge nicht
- Wir sollten jede Liste nur einmal analysieren.
Antworten:
Wenn
Der folgende Algorithmus wäre die Lösung.
Erstens die Zahlen. Angenommen, die erste Liste ist lang
a+c
und die zweite ist langb+c
, wobeic
die Länge ihres gemeinsamen "Schwanzes" (nach dem Zusammenführungspunkt) ist. Bezeichnen wir sie wie folgt:Da wir die Länge nicht kennen, berechnen wir
x
undy
ohne zusätzliche Iterationen; Du wirst sehen wie.Dann iterieren wir jede Liste und kehren sie während der Iteration um! Wenn beide Iteratoren gleichzeitig den Zusammenführungspunkt erreichen, finden wir dies durch bloßen Vergleich heraus. Andernfalls erreicht ein Zeiger den Zusammenführungspunkt vor dem anderen.
Wenn der andere Iterator danach den Zusammenführungspunkt erreicht, wird er nicht zum gemeinsamen Ende weitergeleitet. Gehen Sie stattdessen zum vorherigen Anfang der Liste zurück, der zuvor den Zusammenführungspunkt erreicht hatte! Bevor es das Ende der geänderten Liste erreicht (dh den früheren Anfang der anderen Liste), wird er die
a+b+1
Iterationen insgesamt durchführen. Nennen wir esz+1
.Der Zeiger, der zuerst den Zusammenführungspunkt erreicht hat, wird so lange wiederholt, bis das Ende der Liste erreicht ist. Die Anzahl der durchgeführten Iterationen sollte berechnet werden und ist gleich
x
.Dieser Zeiger iteriert dann zurück und kehrt die Listen erneut um. Aber jetzt geht es nicht mehr zum Anfang der Liste zurück, von der es ursprünglich ausgegangen ist! Stattdessen wird es an den Anfang der anderen Liste gehen! Die Anzahl der durchgeführten Iterationen sollte berechnet werden und gleich sein
y
.Wir kennen also folgende Zahlen:
Daraus bestimmen wir das
Welches löst das Problem.
quelle
Das Folgende ist bei weitem das Größte, was ich je gesehen habe - O (N), keine Zähler. Ich habe es während eines Interviews mit einem SN-Kandidaten bei VisionMap bekommen .
Machen Sie einen Interaktionszeiger wie folgt: Er geht jedes Mal bis zum Ende vorwärts und springt dann zum Anfang der gegenüberliegenden Liste und so weiter. Erstellen Sie zwei davon und zeigen Sie auf zwei Köpfe. Stellen Sie jeden der Zeiger jedes Mal um 1 vor, bis sie sich treffen. Dies geschieht entweder nach ein oder zwei Durchgängen.
Ich benutze diese Frage immer noch in den Interviews - aber um zu sehen, wie lange jemand braucht, um zu verstehen, warum diese Lösung funktioniert.
quelle
a-b-c-x-y-z
undp-q-x-y-z
. Pfad des ersten Zeigersa,b,c,x,y,z,p,q,x
, Pfad des zweiten Zeigersp,q,x,y,z,a,b,c,x
Die Antwort von Pavel erfordert eine Änderung der Listen sowie eine zweimalige Wiederholung jeder Liste.
Hier ist eine Lösung, die nur erfordert , dass jede Liste iterieren zweimal (das erste Mal ihre Länge zu berechnen, wenn die Länge gegeben ist man nur Iterierte muß einmal).
Die Idee ist, die Starteinträge der längeren Liste zu ignorieren (Zusammenführungspunkt kann nicht vorhanden sein), sodass die beiden Zeiger den gleichen Abstand vom Ende der Liste haben. Bewegen Sie sie dann vorwärts, bis sie zusammengeführt werden.
Dies ist asymptotisch die gleiche (lineare Zeit) wie meine andere Antwort, hat aber wahrscheinlich kleinere Konstanten und ist daher wahrscheinlich schneller. Aber ich denke meine andere Antwort ist cooler.
quelle
Nun, wenn Sie wissen, dass sie verschmelzen werden:
Angenommen, Sie beginnen mit:
1) Gehen Sie die erste Liste durch und setzen Sie jeden nächsten Zeiger auf NULL.
Jetzt hast du:
2) Gehen Sie nun die zweite Liste durch und warten Sie, bis Sie eine NULL sehen, das ist Ihr Zusammenführungspunkt.
Wenn Sie nicht sicher sind, ob sie zusammengeführt werden, können Sie einen Sentinel-Wert für den Zeigerwert verwenden, aber das ist nicht so elegant.
quelle
Wenn wir Listen genau zweimal durchlaufen könnten, könnte ich eine Methode zur Bestimmung des Zusammenführungspunkts bereitstellen:
quelle
Hier ist eine Lösung, die rechnerisch schnell ist (jede Liste wird einmal wiederholt), aber viel Speicher benötigt:
quelle
Sie können eine Reihe von Knoten verwenden. Durchlaufen Sie eine Liste und fügen Sie jeden Knoten dem Satz hinzu. Durchlaufen Sie dann die zweite Liste und überprüfen Sie bei jeder Iteration, ob der Knoten in der Gruppe vorhanden ist. Wenn ja, haben Sie Ihren Zusammenführungspunkt gefunden :)
quelle
Dies verstößt möglicherweise gegen die Bedingung "Jede Liste nur einmal analysieren", implementiert jedoch den Schildkröten- und Hasenalgorithmus (der zum Ermitteln des Zusammenführungspunkts und der Zykluslänge einer zyklischen Liste verwendet wird), sodass Sie bei Liste A beginnen und bei Erreichen von NULL die Am Ende tun Sie so, als wäre es ein Zeiger auf den Anfang von Liste B, wodurch das Erscheinungsbild einer zyklischen Liste entsteht. Der Algorithmus sagt Ihnen dann genau, wie weit unten in Liste A die Zusammenführung liegt (die Variable 'mu' gemäß der Wikipedia-Beschreibung).
Außerdem gibt der Wert "Lambda" die Länge von Liste B an. Wenn Sie möchten, können Sie die Länge von Liste A während des Algorithmus berechnen (wenn Sie den NULL-Link umleiten).
quelle
Vielleicht bin ich damit fertig, dies zu vereinfachen, aber einfach die kleinste Liste zu iterieren und die letzten Knoten
Link
als Zusammenführungspunkt zu verwenden?Wo
Data->Link->Link == NULL
ist also der Endpunkt, derData->Link
als Zusammenführungspunkt angegeben wird (am Ende der Liste)?BEARBEITEN:
Okay, von dem Bild, das Sie gepostet haben, analysieren Sie die beiden Listen, die kleinste zuerst. Mit der kleinsten Liste können Sie die Verweise auf den folgenden Knoten pflegen. Wenn Sie nun die zweite Liste analysieren, führen Sie einen Vergleich der Referenz durch, um herauszufinden, wo Referenz [i] die Referenz unter LinkedList [i] -> Link ist. Dies gibt den Zusammenführungspunkt. Zeit, mit Bildern zu erklären (überlagern Sie die Werte auf dem Bild mit dem OP).
Sie haben eine verknüpfte Liste (Referenzen siehe unten):
A->B->C->D->E
Sie haben eine zweite verknüpfte Liste:
1->2->
Mit der zusammengeführten Liste würden die Referenzen dann wie folgt lauten:
1->2->D->E->
Daher ordnen Sie die erste "kleinere" Liste zu (da die zusammengeführte Liste, die wir zählen, eine Länge von 4 und die Hauptliste 5 hat)
Durchlaufen Sie die erste Liste und pflegen Sie eine Referenz mit Referenzen.
Die Liste enthält die folgenden Referenzen
Pointers { 1, 2, D, E }
.Wir gehen nun die zweite Liste durch:
Sicher, Sie pflegen eine neue Liste von Zeigern, aber das liegt nicht außerhalb der Spezifikation. Die erste Liste wird jedoch genau einmal analysiert, und die zweite Liste wird nur dann vollständig analysiert, wenn kein Zusammenführungspunkt vorhanden ist. Andernfalls wird es früher beendet (am Zusammenführungspunkt).
quelle
Ich habe einen Zusammenführungsfall auf meinem FC9 x86_64 getestet und drucke jede Knotenadresse wie unten gezeigt aus:
Hinweis: Da ich die Knotenstruktur ausgerichtet habe, wird bei malloc () einem Knoten die Adresse mit 16 Bytes ausgerichtet, siehe die mindestens 4 Bits. Die kleinsten Bits sind 0s, dh 0x0 oder 000b. Wenn Sie sich also auch im selben Sonderfall befinden (ausgerichtete Knotenadresse), können Sie diese mindestens 4 Bits verwenden. Wenn Sie beispielsweise beide Listen von Kopf bis Ende durchlaufen, setzen Sie 1 oder 2 der 4 Bits der Adresse des besuchenden Knotens, dh setzen Sie ein Flag.
Beachten Sie, dass die obigen Flags nicht die tatsächliche Knotenadresse beeinflussen, sondern nur Ihren SAVED-Knotenzeigerwert.
Sobald jemand gefunden hat, der die Flag-Bits gesetzt hat, sollte der erste gefundene Knoten der Zusammenführungspunkt sein. Anschließend stellen Sie die Knotenadresse wieder her, indem Sie die von Ihnen gesetzten Flag-Bits löschen. Wichtig ist jedoch, dass Sie beim Iterieren (z. B. node = node-> next) vorsichtig sein sollten, um die Reinigung durchzuführen. Denken Sie daran, dass Sie Flag-Bits gesetzt haben. Gehen Sie also so vor
Da dieser Vorschlag die geänderten Knotenadressen wiederherstellt, kann er als "keine Änderung" betrachtet werden.
quelle
Es kann eine einfache Lösung geben, erfordert jedoch einen zusätzlichen Raum. Die Idee ist, eine Liste zu durchlaufen und jede Adresse in einer Hash-Map zu speichern, nun die andere Liste zu durchlaufen und abzugleichen, ob die Adresse in der Hash-Map liegt oder nicht. Jede Liste wird nur einmal durchlaufen. Es gibt keine Änderung an einer Liste. Länge ist noch unbekannt. Verwendeter Hilfsraum: O (n) wobei 'n' die Länge der ersten durchquerten Liste ist.
quelle
Diese Lösung wiederholt jede Liste nur einmal ... es ist auch keine Änderung der Liste erforderlich. Sie können sich jedoch über den Speicherplatz beschweren.
1) Grundsätzlich iterieren Sie in Liste1 und speichern die Adresse jedes Knotens in einem Array (in dem der vorzeichenlose int-Wert gespeichert ist).
2) Dann iterieren Sie list2 und durchsuchen für jede Knotenadresse ---> das Array, ob Sie eine Übereinstimmung finden oder nicht ... wenn Sie dies tun, ist dies der zusammengeführte Knoten
Hoffe es ist eine gültige Lösung ...
quelle
Es ist nicht erforderlich, eine Liste zu ändern. Es gibt eine Lösung, bei der wir jede Liste nur einmal durchlaufen müssen.
quelle
quelle
Hier ist naive Lösung, keine Notwendigkeit, ganze Listen zu durchlaufen.
wenn Ihr strukturierter Knoten drei Felder wie hat
Angenommen, Sie haben zwei Köpfe (Kopf1 und Kopf2), die auf den Kopf von zwei Listen zeigen.
Durchlaufen Sie beide Listen im gleichen Tempo und setzen Sie das Flag = 1 (besuchtes Flag) für diesen Knoten.
quelle
Wie wäre es damit:
Wenn Sie jede Liste nur einmal durchlaufen dürfen, können Sie einen neuen Knoten erstellen, die erste Liste durchlaufen, damit jeder Knoten auf diesen neuen Knoten zeigt, und die zweite Liste durchlaufen, um festzustellen, ob ein Knoten auf Ihren neuen Knoten zeigt ( das ist dein Zusammenführungspunkt). Wenn die zweite Durchquerung nicht zu Ihrem neuen Knoten führt, haben die ursprünglichen Listen keinen Zusammenführungspunkt.
Wenn Sie die Listen mehrmals durchlaufen dürfen, können Sie jede Liste durchlaufen, um ihre Länge zu ermitteln. Wenn sie unterschiedlich sind, lassen Sie die "zusätzlichen" Knoten am Anfang der längeren Liste weg. Durchlaufen Sie dann einfach beide Listen Schritt für Schritt und suchen Sie den ersten Zusammenführungsknoten.
quelle
Schritte in Java:
quelle
Wir können es effizient lösen, indem wir das Feld "isVisited" einführen. Durchlaufen Sie die erste Liste und setzen Sie den Wert "isVisited" für alle Knoten bis zum Ende auf "true". Beginnen Sie nun mit dem zweiten und suchen Sie den ersten Knoten, an dem das Flag wahr ist, und Boom, Ihren Zusammenführungspunkt.
quelle
Schritt 1: Finden Sie die Länge beider Listen. Schritt 2: Finden Sie das Diff und verschieben Sie die größte Liste mit dem Unterschied. Schritt 3: Jetzt befinden sich beide Listen in einer ähnlichen Position. Schritt 4: Durchlaufen Sie die Liste, um den Zusammenführungspunkt zu finden
quelle
quelle
Verwenden Sie Map oder Dictionary, um die Adresse gegen den Wert des Knotens zu speichern. Wenn die bereits vorhandene Adresse in der Karte / im Wörterbuch vorhanden ist, ist der Wert des Schlüssels die Antwort. Ich war das:
quelle
AO (n) Komplexitätslösung. Aber basierend auf einer Annahme.
Annahme ist: Beide Knoten haben nur positive ganze Zahlen.
Logik: Machen Sie die ganze Ganzzahl von Liste1 zu negativ. Gehen Sie dann durch die Liste2, bis Sie eine negative Ganzzahl erhalten. Einmal gefunden => nimm es, ändere das Vorzeichen wieder auf positiv und kehre zurück.
quelle
Wir können zwei Zeiger verwenden und uns so bewegen, dass wenn einer der Zeiger null ist, wir ihn auf den Kopf der anderen Liste und für den anderen auf dieselbe zeigen. Wenn die Listenlängen unterschiedlich sind, treffen sie sich auf diese Weise im zweiten Durchgang . Wenn die Länge von Liste1 n und Liste2 m ist, ist ihre Differenz d = abs (nm). Sie werden diese Strecke zurücklegen und sich am Zusammenführungspunkt treffen.
Code:
quelle
Sie können die Knoten von
list1
zu einem Hashset und die Schleife durch die Sekunde hinzufügen. Wenn bereits ein Knoten vonlist2
in der Menge vorhanden ist. Wenn ja, dann ist dies der Zusammenführungsknotenquelle
Lösung mit Javascript
quelle
Wenn das Bearbeiten der verknüpften Liste zulässig ist,
quelle