wake-up-neo.com

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

Diese Frage mag alt sein, aber mir fällt keine Antwort ein.

Angenommen, es gibt zwei Listen mit unterschiedlichen Längen: an einem Punkt ; Woher wissen wir, wo sich der Verschmelzungspunkt befindet?

Bedingungen:

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

Example of two merged linked lists.

81
rplusg

Ob

  • mit "Änderung ist nicht zulässig" war gemeint "Sie können sich ändern, aber am Ende sollten sie wiederhergestellt werden" und
  • wir könnten die Listen genau wiederholen zweimal

der folgende Algorithmus wäre die Lösung.

Zuerst die Zahlen. Angenommen, die erste Liste hat die Länge a+c und die zweite hat die Länge b+c, wobei c die Länge ihres gemeinsamen "Endes" (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 x und y 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, werden wir dies durch bloßen Vergleich feststellen. Andernfalls erreicht ein Zeiger den Zusammenführungspunkt vor dem anderen.

Wenn danach der andere Iterator den Zusammenführungspunkt erreicht, wird er nicht zum gemeinsamen Endpunkt weitergeleitet. Stattdessen wird an den vorherigen Anfang der Liste zurückgekehrt, der zuvor den Zusammenführungspunkt erreicht hatte! Bevor er also das Ende der geänderten Liste erreicht (d. H. Den früheren Anfang der anderen Liste), wird er insgesamt a+b+1-Iterationen vornehmen. 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.

Dann führt dieser Zeiger eine Iteration durch und kehrt die Listen erneut um. Aber jetzt geht es nicht an den Anfang der Liste zurück, von der es ursprünglich angefangen hat! Stattdessen geht es an den Anfang der anderen Liste! Die Anzahl der durchgeführten Iterationen sollte berechnet werden und gleich y sein.

Wir kennen also folgende Nummern:

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

Woraus wir das bestimmen

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

Was löst das Problem.

35
P Shved

Das Folgende ist bei weitem das Größte, was ich gesehen habe - O (N), keine Zähler. Ich bekam es während eines Interviews mit einem Kandidaten S.N. bei VisionMap .

Mache einen Zwischenzeiger wie diesen: Er geht jedes Mal bis zum Ende vor und springt dann an den Anfang der gegenüberliegenden Liste, usw. Erzeuge zwei davon und zeige auf zwei Köpfe. Stellen Sie die Zeiger jedes Mal um 1 vor, bis sie sich treffen. Dies geschieht entweder nach einem oder zwei Durchgängen.

Ich benutze diese Frage immer noch in den Interviews - aber um zu sehen, wie lange es dauert, um zu verstehen, warum diese Lösung funktioniert.

113

Die Antwort von Pavel erfordert eine Änderung der Listen sowie, die jede Liste zweimal wiederholen.

Hier ist eine Lösung, die erfordert, dass nur jede Liste zweimal durchlaufen muss (das erste Mal, um ihre Länge zu berechnen; wenn die Länge angegeben wird, müssen Sie nur einmal durchlaufen).

Die Idee ist, die Starteinträge der längeren Liste zu ignorieren (Zusammenführungspunkt kann nicht da sein), so dass die beiden Zeiger vom Ende der Liste gleich weit entfernt sind. Bewegen Sie sie dann nach vorne, bis sie zusammenfließen.

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 das gleiche (lineare Zeit) wie meine andere Antwort, hat aber wahrscheinlich kleinere Konstanten, ist also wahrscheinlich schneller. Aber ich denke, meine andere Antwort ist cooler.

88
Artelius

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 den 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 Zeigerwert für den Zeigerwert verwenden. Dies ist jedoch nicht so elegant.

27
tster

Wenn wir die Listen genau zweimal durchlaufen könnten, kann ich die Methode zum Bestimmen des Zusammenführungspunkts angeben:

  • iterieren Sie beide Listen und berechnen Sie die Längen A und B
  • berechnung der Längenunterschiede C = | A-B |;
  • beginnen Sie, beide Listen gleichzeitig zu durchlaufen, machen Sie jedoch zusätzliche C-Schritte auf der Liste, die größer waren
  • diese beiden Zeiger treffen sich am Verschmelzungspunkt 
12
rachvela

Hier ist eine Lösung, die rechnerisch schnell ist (jede Liste einmal durchläuft), jedoch viel Speicherplatz 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
7
Skizz

Dies verstößt wohl gegen die Bedingung "Jede Liste nur einmal analysieren", implementiere jedoch den Algorithmus tortoise und hase (wird verwendet, um den Zusammenführungspunkt und die Zykluslänge einer zyklischen Liste zu ermitteln), so dass Sie bei Liste A beginnen, und wenn Sie diese erreichen Die NULL am Ende, die Sie so tun, als sei sie ein Zeiger auf den Anfang von Liste B, wodurch das Erscheinungsbild einer zyklischen Liste erzeugt wird. Der Algorithmus sagt Ihnen dann genau, wie weit unten in Liste A die Zusammenführung ist (die Variable 'mu' gemäß der Wikipedia-Beschreibung).

Der "Lambda" -Wert gibt auch die Länge der Liste B an. Wenn Sie möchten, können Sie die Länge der Liste A während des Algorithmus ermitteln (wenn Sie den NULL-Link umleiten).

6
Artelius

Sie können eine Reihe von Knoten verwenden. Durchlaufen Sie eine Liste und fügen Sie jeden Knoten zum Satz hinzu. Durchlaufen Sie dann die zweite Liste und prüfen Sie bei jeder Wiederholung, ob der Knoten im Satz vorhanden ist. Wenn ja, haben Sie Ihren Zusammenführungspunkt gefunden :)

5
isyi

Ich habe einen Merge-Fall auf meinem FC9 x86_64 getestet und drucke jede Knotenadresse wie folgt:

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


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

Beachten Sie, da ich die Knotenstruktur ausgerichtet habe. Wenn malloc () ein Knoten ist, wird die Adresse mit 16 Bytes ausgerichtet, siehe mindestens 4 Bits. Die kleinsten Bits sind 0s, dh 0x0 oder 000b . Wenn Sie sich also im selben Sonderfall befinden (ausgerichtete Knotenadresse), können Sie diese mindestens 4 Bits verwenden Zum Beispiel, wenn beide befahren werden Listen von Kopf bis Ende, setzen Sie 1 oder 2 der 4 Bits der Adresse des Besucherknotens, dh setzen Sie ein Flag;

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

Beachten Sie, dass die obigen Flags nicht die reale Knotenadresse betreffen, sondern nur Ihren SAVED-Knotenzeigerwert.

Wenn jemand gefunden hat, dass er die Flag-Bit (s) gesetzt hat, sollte der erste gefundene Knoten der Zusammenführungspunkt sein. Anschließend können Sie die Knotenadresse wiederherstellen, indem Sie die von Ihnen gesetzten Flag-Bits löschen. Wichtig ist jedoch, dass Sie bei der Wiederholung (z. B. node = node-> next) vorsichtig sein sollten, um die Bereinigung durchzuführen. Denken Sie daran, dass Sie Flag-Bits gesetzt haben 

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

Da mit diesem Vorschlag die geänderten Knotenadressen wiederhergestellt werden, kann dies als "keine Änderung" betrachtet werden.

3
Test

Vielleicht bin ich über die Vereinfachung hinaus, aber iteriere einfach die kleinste Liste und verwende die letzten Knoten Link als Zusammenführungspunkt.

Dabei ist Data->Link->Link == NULL der Endpunkt und gibt Data->Link als Zusammenführungspunkt (am Ende der Liste) an.

BEARBEITEN:

Okay, aus dem Bild, das Sie gepostet haben, parsen 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, vergleichen Sie die Referenz, um herauszufinden, wo Referenz [i] die Referenz bei LinkedList [i] -> Link ist. Dies gibt den Zusammenführungspunkt an. Zeit, um es 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->

Bei der zusammengeführten Liste würden die Referenzen dann wie folgt aussehen:

1->2->D->E->

Daher ordnen Sie die erste "kleinere" Liste zu (wie die zusammengeführte Liste, die wir zählen, eine Länge von 4 hat und die Hauptliste 5).

Blättern Sie durch die erste Liste, und pflegen Sie eine Referenzreferenz.

Die Liste enthält die folgenden Referenzen Pointers { 1, 2, D, E }.

Wir gehen jetzt 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 es keinen Zusammenführungspunkt gibt. Andernfalls endet es früher (am Zusammenführungspunkt).

3
Kyle Rozendo

diese Lösung durchläuft jede Liste nur einmal. Auch eine Änderung der Liste ist nicht erforderlich. Sie können sich jedoch über den Platz beschweren.
1) Im Grunde iterieren Sie in list1 und speichern die Adresse jedes Knotens in einem Array (das den vorzeichenlosen int-Wert speichert)
2) Dann iterieren Sie list2, und nach der Adresse jedes Knotens ---> durchsuchen Sie das Array, das Sie finden, oder nicht

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

2
rajya vardhan

Es kann eine einfache Lösung geben, erfordert aber einen zusätzlichen Platz. Die Idee ist, eine Liste zu durchlaufen und jede Adresse in einer Hash-Map zu speichern. Nun durchqueren Sie die andere Liste und stimmen überein, ob die Adresse in der Hash-Map liegt. 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 durchlaufenen Liste ist.

1
Vikas Agarwal

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

  1. Erstellen Sie zwei Stapel, sagen wir stck1 und stck2.
  2. Durchqueren Sie die 1. Liste und drücken Sie eine Kopie jedes Knotens, den Sie in stck1 durchlaufen.
  3. Wie Schritt 2, aber durchqueren Sie dieses Mal die 2. Liste und drücken Sie die Kopie der Knoten in stck2.
  4. Pop aus beiden Stapeln und prüfe, ob die beiden Knoten gleich sind. Wenn ja, dann verweise auf sie. Wenn nein, sind vorherige Knoten, die gleich waren, tatsächlich der Zusammenführungspunkt, nach dem wir gesucht haben.
1
ABVash

Hier ist eine naive Lösung: Es ist nicht nötig, ganze Listen zu durchqueren.

wenn Ihr strukturierter Knoten drei Felder hat, wie

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

angenommen, Sie haben zwei Köpfe (head1 und head2), die auf den Kopf zweier Listen zeigen.

Durchquere die Liste mit der gleichen Geschwindigkeit und setze die Markierung = 1 (besuchte Flagge) für diesen Knoten. 

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

Verwenden Sie Map oder Dictionary, um die Adresse gegen den Wert des Knotens zu speichern. Wenn die Adresse bereits in der Map/Dictionary vorhanden ist, ist der Wert des Schlüssels die Antwort.

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;
}
0
Vishal Anand

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, um jeden Knoten auf diesen neuen Knoten zu zeigen, und die zweite Liste, um zu sehen, ob ein Knoten auf Ihren neuen Knoten zeigt ( das ist dein Zusammenführungspunkt). Wenn der zweite Durchlauf 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 nach ihren Längen durchsuchen. Wenn sie unterschiedlich sind, lassen Sie die "zusätzlichen" Knoten am Anfang der längeren Liste aus. Durchlaufen Sie dann beide Listen Schritt für Schritt und finden Sie den ersten zusammenführenden Knoten.

0
user2024069

Schritt 1: Suche die Länge beider Listen Schritt 2: Finde den Unterschied und verschiebe die größte Liste mit dem Unterschied Schritt 3: Jetzt befinden sich beide Listen in einer ähnlichen Position 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
0
svaithin

Schritte in Java:

  1. Erstellen Sie eine Karte. 
  2. Beginnen Sie das Durchqueren in den beiden Zweigen der Liste. Fügen Sie alle durchquerten Knoten der Liste in die Map ein. Verwenden Sie dazu ein eindeutiges Element, das sich auf Knoten (etwa Knoten-ID) bezieht, und geben Sie Werte als 1 für alle ein.
  3. Erhöhen Sie den Wert dieses Schlüssels, wenn zum ersten Mal ein doppelter Schlüssel kommt (sagen wir jetzt, sein Wert wurde zu 2, was> 1 ist).
  4. Rufen Sie den Schlüssel ab, bei dem der Wert größer als 1 ist. Dies sollte der Knoten sein, an dem zwei Listen zusammengeführt werden. 
0
King KB

Das ist ein echtes Problem! Wenn wir eine Baumstruktur in SQL-Datenbank haben. Wir wollen die LCA in einem SQL-Trigger finden.

In der Trigger-Umgebung können wir keine temporäre Tabelle erstellen, da die Transaktion implizit festgeschrieben wird. Also müssen wir es im O(1) Speicher tun, d. H. Wir können nur Variable verwenden.

0
Kai Liu

Eine O(n) Komplexitätslösung. Aber basierend auf einer Annahme.

annahme ist: Beide Knoten haben nur positive ganze Zahlen.

logic: alle ganzen Zahlen von list1 auf negativ setzen. Gehen Sie dann durch die Liste2, bis Sie eine negative Ganzzahl erhalten. Sobald gefunden => nimm es, ändere das Vorzeichen wieder in 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;
    }

}
0
user3828943
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;
}
0
Yachana Yachana

Wir können es effizient lösen, indem wir das Feld "isVisited" einführen. Die erste Liste durchlaufen und den Wert "isVisited" für alle Knoten bis zum Ende auf "true" setzen. Beginnen Sie jetzt mit dem zweiten Knoten und suchen Sie den ersten Knoten, bei dem Flag wahr ist, und Boom ist Ihr Zusammenführungspunkt.

0
Riya kathil