Überprüfen Sie, ob zwei verknüpfte Listen zusammengeführt werden. Wenn ja, wo?

101

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:

  1. Wir kennen die Länge nicht
  2. Wir sollten jede Liste nur einmal analysieren.

Beispiel für zwei zusammengeführte verknüpfte Listen.

rplusg
quelle
Zusammenführen bedeutet, dass ab diesem Punkt nur noch eine Liste vorhanden ist.
rplusg
Ist eine Änderung der Liste zulässig?
Artelius
1
Ich bin mir ziemlich sicher, dass es ohne Änderung der Liste nicht funktioniert. (Oder kopieren Sie es einfach woanders hin, um die Einschränkung zu vermeiden, es nur einmal zu analysieren.)
Georg Schölly
2
Könnte der Punkt gewesen sein. Verdammte Interviewer! Hehe
Kyle Rosendo
1
Ich habe einen interessanten Vorschlag ... vorausgesetzt, der gemeinsame Schwanz der Liste ist unendlich lang. Wie können Sie den Knotenpunkt mit konstantem Speicher finden?
Akusete

Antworten:

36

Wenn

  • mit "Änderung ist nicht erlaubt" war gemeint "Sie können ändern, aber am Ende sollten sie wiederhergestellt werden", und
  • Wir könnten die Listen genau zweimal durchlaufen

Der folgende Algorithmus wäre die Lösung.

Erstens die Zahlen. Angenommen, die erste Liste ist lang a+cund die zweite ist lang b+c, wobei cdie Länge ihres gemeinsamen "Schwanzes" (nach dem Zusammenführungspunkt) ist. Bezeichnen wir sie wie folgt:

x = a+c
y = b+c

Da wir die Länge nicht kennen, berechnen wir xund yohne 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+1Iterationen insgesamt durchführen. Nennen wir es z+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:

x = a+c
y = b+c
z = a+b

Daraus bestimmen wir das

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

Welches löst das Problem.

P Shved
quelle
2
Kommentar zum Fragestatus Änderung der Liste nicht erlaubt!
Skizz
1
Ich mag diese Antwort (sehr kreativ). Das einzige Problem, das ich damit habe, ist, dass davon ausgegangen wird, dass Sie die Länge beider Listen kennen.
Tster
Sie können die Liste nicht ändern, und wir kennen die Länge nicht - dies sind die Einschränkungen ... wie auch immer, danke für eine kreative Antwort.
rplusg
2
@tster, @calvin, die Antwort geht nicht davon aus, wir brauchen die Länge. Es kann inline berechnet werden. Erklärungen zu meinen Antworten hinzufügen.
P Shved
2
@Forethinker, das besuchte Knoten hasht und / oder sie als gesehen markiert, erfordert O-Speicher (Listenlänge), während viele Lösungen (einschließlich meiner, wie unvollkommen und kompliziert sie auch sein mögen) O-Speicher (1) benötigen.
P Shved
155

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.

Pavel Radzivilovsky
quelle
6
das ist einfach genial!
Cong Hui
2
Dies ist eine gute Antwort, aber Sie müssen die Listen zweimal durchgehen, was gegen Bedingung 2 verstößt.
Tster
2
Ich finde diese Lösung ziemlich elegant, wenn ein Zusammenführungspunkt garantiert vorhanden ist. Es funktioniert nicht, um Zusammenführungspunkte zu erkennen. Wenn einer nicht vorhanden ist, wird eine Endlosschleife ausgeführt.
Wechsel Richtung
4
Das ist super genial! Erklärung: Wir haben 2 Listen: a-b-c-x-y-zund p-q-x-y-z. Pfad des ersten Zeigers a,b,c,x,y,z,p,q,x, Pfad des zweiten Zeigersp,q,x,y,z,a,b,c,x
Nikolai Golub
14
Brillant. Für diejenigen, die nicht verstanden haben, zählen Sie die Anzahl der Knoten, die von head1-> tail1 -> head2 -> Schnittpunkt und head2 -> tail2-> head1 -> Schnittpunkt zurückgelegt wurden. Beide sind gleich (Zeichnen Sie verschiedene Arten von verknüpften Listen, um dies zu überprüfen). Grund dafür ist, dass beide Zeiger die gleichen Entfernungen zurücklegen müssen head1-> IP + head2-> IP, bevor sie wieder IP erreichen. Wenn also IP erreicht ist, sind beide Zeiger gleich und wir haben den Zusammenführungspunkt.
Adev
91

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.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

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.

Artelius
quelle
4
Heute, als wir Wodka tranken, schlug ich diese Frage einem Freund von mir vor, und er gab die gleiche Antwort wie Ihre und bat darum, sie auf SO zu posten. Aber du scheinst der Erste zu sein. Also mache ich eine +1 für dich von mir und ich wünschte, ich könnte noch eine +1 machen.
P Shved
2
+1 wie dieses und benötigt auch keine Änderung an der Liste, auch die meisten Implementierungen von verknüpften Listen sehen normalerweise Länge vor
keshav84
3
Wir haben zu viele Pavels. Meine Lösung erfordert keine Änderung der Liste.
Pavel Radzivilovsky
Gute Antwort. Was wird die zeitliche Komplexität dafür sein. 0 (n + m)? wobei n = Knoten in Liste 1, m = Knoten in Liste 2?
Vihaan Verma
anstatt beide Zeiger in beiden Listen zu verschieben: Wir können nur sehen, ob der Diff> = klein von zwei Pfaden ist, wenn ja, dann in einer kleinen Liste um einen kleinen Wert verschieben, andernfalls in einer kleinen Liste um einen Diff + 1-Wert verschieben; Wenn diff 0 ist, ist der letzte Knoten die Antwort.
Vishal Anand
30

Nun, wenn Sie wissen, dass sie verschmelzen werden:

Angenommen, Sie beginnen mit:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1) Gehen Sie die erste Liste durch und setzen Sie jeden nächsten Zeiger auf NULL.

Jetzt hast du:

A   B   C

1-->2-->3   4   5

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.

tster
quelle
3
Sie zerstören jedoch die Liste in dem Prozess, um nie wieder verwendet zu werden: P
Kyle Rosendo
@ Kyle Rozendo, meine Lösung ändert Listen so, wie sie nach der Verarbeitung wiederhergestellt werden können. Dies ist jedoch eine klarere Demonstration des Konzepts
P Shved
Ich habe nicht gesehen, dass eine Änderung der Liste nicht erlaubt war. Ich werde es mir überlegen, aber mir fällt nichts ein, ohne jeden gesehenen Knoten zu speichern.
Tster
10
Komm schon, das ist die richtige Antwort! Wir müssen nur die Frage anpassen :)
P Shved
23
Hervorragender Algorithmus zur Erzeugung von Speicherlecks.
Karoly Horvath
14

Wenn wir Listen genau zweimal durchlaufen könnten, könnte ich eine Methode zur Bestimmung des Zusammenführungspunkts bereitstellen:

  • Iterieren Sie beide Listen und berechnen Sie die Längen A und B.
  • Längendifferenz berechnen C = | AB |;
  • Starten Sie die gleichzeitige Iteration beider Listen, führen Sie jedoch zusätzliche C-Schritte in der Liste aus, die größer waren
  • Diese beiden Zeiger treffen sich im Zusammenführungspunkt
Rachvela
quelle
8

Hier ist eine Lösung, die rechnerisch schnell ist (jede Liste wird einmal wiederholt), aber viel Speicher benötigt:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item
Skizz
quelle
2
Dies entspricht der zweimaligen Verarbeitung einer Liste.
Georg Schölly
Ich nehme an, dass Sie technisch gesehen zweimal mit den Listen arbeiten, aber es ist eine signifikante Verbesserung der Lösung von Kyle Rozendo. Wenn nun "Verarbeiten der Liste" als "Lesen des Verknüpfungswerts und Folgen des Zeigers" definiert ist, könnte argumentiert werden, dass die Liste einmal verarbeitet wird - jeder Verknüpfungswert wird einmal gelesen, gespeichert und dann verglichen.
Skizz
Wird definitiv schneller sein als meine, kein Zweifel.
Kyle Rosendo
7

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

isyi
quelle
Ich befürchte (aufgrund von Ω (n) zusätzlichem Speicherplatz), dass dies der einzige Ansatz ist (nicht die Liste (n) neu zu erstellen und) eine Liste nicht mehr als einmal zu analysieren. Das Erkennen einer Schleife in der Liste ist für die erste Liste trivial (prüfen Sie, ob der Knoten festgelegt ist). Verwenden Sie eine beliebige Schleifenerkennungsmethode in der zweiten Liste, um die Beendigung sicherzustellen. (Bei der Interviewfrage ging es möglicherweise darum , einer Problemstellung genau zuzuhören und nicht mit einem Hammer
einzuspringen, von dem
6

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

Artelius
quelle
So ziemlich das, was ich gesagt habe, nur mit schickeren Namen. : P
Kyle Rosendo
Überhaupt nicht. Diese Lösung ist O (n) in Operationen und O (1) in der Speichernutzung (tatsächlich sind nur zwei Zeigervariablen erforderlich).
Artelius
Ja, hätte meinen vorherigen Kommentar löschen sollen, da sich meine Lösung etwas geändert hat. Hehe.
Kyle Rosendo
Aber ich sehe nicht, wie das überhaupt zutraf?
Artelius
Ihre Erklärung hat es getan, nicht der Algorithmus selbst. Vielleicht sehe ich das anders, aber hey.
Kyle Rosendo
3

Vielleicht bin ich damit fertig, dies zu vereinfachen, aber einfach die kleinste Liste zu iterieren und die letzten Knoten Linkals Zusammenführungspunkt zu verwenden?

Wo Data->Link->Link == NULList also der Endpunkt, der Data->Linkals 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:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

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

Kyle Rosendo
quelle
Nun ändert sich etwas von dem, was ich zuerst sagen wollte, aber von dem, was das OP zu wollen scheint, wird dies den Trick tun.
Kyle Rosendo
Es ist jetzt klarer. Aber linear in der Speichernutzung. Das gefällt mir nicht.
Artelius
Die Frage verlangte nicht mehr, sonst kann der gesamte Prozess multithreaded werden. Dies ist immer noch eine vereinfachte "Top-Level" -Ansicht der Lösung. Der Code kann auf verschiedene Arten implementiert werden. :)
Kyle Rosendo
1
UH, was? Multithreading ist eine Möglichkeit, die Verarbeitungsleistung besser zu nutzen, ohne die Gesamtverarbeitungsleistung zu reduzieren, die ein Algorithmus benötigt. Und zu sagen, dass der Code auf verschiedene Arten implementiert werden kann, ist nur eine Ausrede.
Artelius
1
Dies bringt die "Analyse jeder Liste nur einmal" wirklich auf einen Bruchpunkt. Sie kopieren lediglich eine Liste und vergleichen die andere Liste mit der Kopie.
Skizz
3

Ich habe einen Zusammenführungsfall auf meinem FC9 x86_64 getestet und drucke jede Knotenadresse wie unten gezeigt aus:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

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.

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

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

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

Da dieser Vorschlag die geänderten Knotenadressen wiederherstellt, kann er als "keine Änderung" betrachtet werden.

Prüfung
quelle
+1, das ist es, was natürlich bei "nur einmal iterieren" in den Sinn kommt, keine Ahnung, warum dies nie gewählt wurde! Schöne Lösung.
Jman
3

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.

Vikas Agarwal
quelle
2

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

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
  addr[i]=&p1;
  p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
  if(search(addr[],len,&p2)==1)//match found
  {
    //this is the merging node
    return (p2);
  }
  p2=p2->next;
}

int search(addr,len,p2){
  i=0;  
  while(i<len){
    if(addr[i]==p2)
      return 1;
    i++;
  }
 return 0;
} 

Hoffe es ist eine gültige Lösung ...

Rajya Vardhan
quelle
Dadurch wird eine der Listen mehr als einmal wiederholt, allerdings in Form eines Arrays anstelle der Liste selbst.
Syockit
1

Es ist nicht erforderlich, eine Liste zu ändern. Es gibt eine Lösung, bei der wir jede Liste nur einmal durchlaufen müssen.

  1. Erstellen Sie zwei Stapel, z. B. stck1 und stck2.
  2. Durchlaufen Sie die erste Liste und verschieben Sie eine Kopie jedes Knotens, den Sie in stck1 durchlaufen.
  3. Wie Schritt zwei, aber diesmal die zweite Liste durchlaufen und die Kopie der Knoten in stck2 verschieben.
  4. Öffnen Sie nun beide Stapel und prüfen Sie, ob die beiden Knoten gleich sind. Wenn ja, behalten Sie einen Verweis auf sie bei. Wenn nein, dann sind vorherige Knoten, die gleich waren, tatsächlich der Zusammenführungspunkt, den wir gesucht haben.
ABVash
quelle
1
int FindMergeNode(Node headA, Node headB) {
  Node currentA = headA;
  Node currentB = headB;

  // Do till the two nodes are the same
  while (currentA != currentB) {
    // If you reached the end of one list start at the beginning of the other
    // one currentA
    if (currentA.next == null) {
      currentA = headA;
    } else {
      currentA = currentA.next;
    }
    // currentB
    if (currentB.next == null) {
      currentB = headB;
    } else {
      currentB = currentB.next;
    }
  }
  return currentB.data;
}
Fahad Israr
quelle
In seiner ursprünglichen Version dieses buchstabiert nur die höchste gestimmt Antwort (Pavel Radzivilovsky 2013) .
Graubart
0

Hier ist naive Lösung, keine Notwendigkeit, ganze Listen zu durchlaufen.

wenn Ihr strukturierter Knoten drei Felder wie hat

struct node {
    int data;   
    int flag;  //initially set the flag to zero  for all nodes
    struct node *next;
};

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.

  if (node->next->field==1)//possibly longer list will have this opportunity
      //this will be your required node. 
Anil Kumar Arya
quelle
0

Wie wäre es damit:

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

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

user2024069
quelle
1. ändert nicht nur die erste Liste, sondern zerstört sie. 2. wird immer wieder vorgeschlagen.
Graubart
0

Schritte in Java:

  1. Erstellen Sie eine Karte.
  2. Beginnen Sie mit dem Durchlaufen in beiden Zweigen der Liste und fügen Sie alle durchquerten Knoten der Liste in die Karte ein, indem Sie eine eindeutige Funktion in Bezug auf Knoten (z. B. Knoten-ID) als Schlüssel verwenden, und setzen Sie Werte als 1 für alle.
  3. Wenn der erste doppelte Schlüssel kommt, erhöhen Sie den Wert für diesen Schlüssel (sagen wir jetzt, sein Wert wurde 2, was> 1 ist.
  4. Holen Sie sich den Schlüssel, bei dem der Wert größer als 1 ist, und das sollte der Knoten sein, auf dem zwei Listen zusammengeführt werden.
König KB
quelle
1
Was ist, wenn wir einen Zyklus im zusammengeführten Teil haben?
Rohit
Aber für die Fehlerbehandlungszyklen sieht dies sehr nach Isyis Antwort aus .
Graubart
0

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.

Riya Kathil
quelle
0

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

//Psuedocode
def findmergepoint(list1, list2):
lendiff = list1.length() > list2.length() : list1.length() - list2.length() ? list2.lenght()-list1.lenght()
biggerlist = list1.length() > list2.length() : list1 ? list2  # list with biggest length
smallerlist = list1.length() < list2.length() : list2 ? list1 # list with smallest length


# move the biggest length to the diff position to level both the list at the same position
for i in range(0,lendiff-1):
    biggerlist = biggerlist.next
#Looped only once.  
while ( biggerlist is not None and smallerlist is not None ):
    if biggerlist == smallerlist :
        return biggerlist #point of intersection


return None // No intersection found
Svaithin
quelle
(Ich mochte die Liste mit jedem Element, das eine Zeile beginnt, besser.
Erwägen
0
int FindMergeNode(Node *headA, Node *headB)
{
    Node *tempB=new Node;
    tempB=headB;
   while(headA->next!=NULL)
       {
       while(tempB->next!=NULL)
           {
           if(tempB==headA)
               return tempB->data;
           tempB=tempB->next;
       }
       headA=headA->next;
       tempB=headB;
   }
    return headA->data;
}
Yachana Yachana
quelle
Sie müssen Ihrer Antwort eine Erklärung hinzufügen. Nur-Code-Antworten werden möglicherweise gelöscht.
rghome
0

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:

int FindMergeNode(Node headA, Node headB) {

Map<Object, Integer> map = new HashMap<Object, Integer>();

while(headA != null || headB != null)
{
    if(headA != null && map.containsKey(headA.next))
    {
        return map.get(headA.next);
    }

    if(headA != null && headA.next != null)
    {
         map.put(headA.next, headA.next.data);
         headA = headA.next;
    }

    if(headB != null && map.containsKey(headB.next))
    {
        return map.get(headB.next);
    }

    if(headB != null && headB.next != null)
    {
        map.put(headB.next, headB.next.data);
        headB = headB.next;
    }
}

return 0;
}
Vishal Anand
quelle
0

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.

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

    SinglyLinkedListNode current = head1; //head1 is give to be not null.

    //mark all head1 nodes as negative
    while(true){
        current.data = -current.data;
        current = current.next;
        if(current==null) break;
    }

    current=head2; //given as not null
    while(true){
        if(current.data<0) return -current.data;
        current = current.next;
    }

}
user3828943
quelle
0

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:

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* start1=head1;
    SinglyLinkedListNode* start2=head2;
    while (start1!=start2){
        start1=start1->next;
        start2=start2->next;
        if (!start1)
        start1=head2;
        if (!start2)
        start2=head1;
    }
    return start1->data;
}
Aditya Singh
quelle
0

Sie können die Knoten von list1zu einem Hashset und die Schleife durch die Sekunde hinzufügen. Wenn bereits ein Knoten von list2in der Menge vorhanden ist. Wenn ja, dann ist dies der Zusammenführungsknoten

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    HashSet<SinglyLinkedListNode> set=new HashSet<SinglyLinkedListNode>();
    while(head1!=null)
    {
        set.add(head1);
        head1=head1.next;
    }
    while(head2!=null){
        if(set.contains(head2){
            return head2.data;
        }
    }
    return -1;
}
CB Shivananda
quelle
0

Lösung mit Javascript

var getIntersectionNode = function(headA, headB) {
    
    if(headA == null || headB == null) return null;
    
    let countA = listCount(headA);
    let countB = listCount(headB);
    
    let diff = 0;
    if(countA > countB) {

        diff = countA - countB;
        for(let i = 0; i < diff; i++) {
            headA = headA.next;
        }
    } else if(countA < countB) {
        diff = countB - countA;
        for(let i = 0; i < diff; i++) {
            headB = headB.next;
        }
    }

    return getIntersectValue(headA, headB);
};

function listCount(head) {
    let count = 0;
    while(head) {
        count++;
        head = head.next;
    }
    return count;
}

function getIntersectValue(headA, headB) {
    while(headA && headB) {
        if(headA === headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}
Rama
quelle
0

Wenn das Bearbeiten der verknüpften Liste zulässig ist,

  1. Machen Sie dann einfach die nächsten Knotenzeiger aller Knoten der Liste 2 zu Null.
  2. Ermitteln des Datenwerts des letzten Knotens der Liste 1. Dadurch erhalten Sie den sich überschneidenden Knoten in einer einzelnen Durchquerung beider Listen ohne "HiFi-Logik".
Devvrat Joshi
quelle