Merge Two Sorted Lists

Q: Wie hoch ist die Zeitkomplexität beim Zusammenführen zweier sortierter Listen?

Es ist O(L1 + L2) : Bei jedem Vergleich wird ein Knoten platziert, und kein Knoten wird zweimal platziert. Bei Knotenobjekten benötigt das Zusammenführen O(1) zusätzlichen Speicher, da dabei nur Verknüpfungen geändert werden. Bei den hier verwendeten Arrays benötigt das gemeinsame Verknüpfungsarray O(L1 + L2) Speicher.

LeichtVerkettete Liste Zwei Zeiger

+10

Du erhältst zwei einfach verkettete Listen, die jeweils in zwei Arrays gleicher Länge gespeichert sind. In der ersten Liste enthält Knoten i den Wert values1[i] und verweist auf Knoten next1[i]. Die zweite Liste funktioniert genauso mit next2 und values2. In beiden Listen beendet -1 die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in Listenreihenfolge gespeichert, folge also den Verweisen.

Jede Liste ist entlang ihrer Verweise nicht absteigend sortiert. Führe die beiden zu einer sortierten Liste zusammen und gib ihre Werte der Reihe nach zurück.

Funktion

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: der Index des Knotens, auf den jeder Knoten der ersten Liste verweist, oder -1 für seinen letzten Knoten
values1integer-array: der von jedem Knoten der ersten Liste gehaltene Wert
next2integer-array: der Index des Knotens, auf den jeder Knoten der zweiten Liste verweist, oder -1 für den letzten Knoten der zweiten Liste
values2integer-array: der Wert, der von jedem Knoten der zweiten Liste gehalten wird
Gibt zurückinteger-array: die Werte der zusammengeführten Liste, in Reihenfolge

Einschränkungen

1 ≤ L1 ≤ 2000, wobei L1 die Länge von next1 und values1 ist.
1 ≤ L2 ≤ 2000, wobei L2 die Länge von next2 und values2 ist.
-1000 ≤ values1[i], values2[j] ≤ 1000
Jeder Eintrag von next1 ist -1 oder ein Knotenindex der ersten Liste, und jeder Eintrag von next2 ist -1 oder ein Knotenindex der zweiten Liste.
Beginnend beim Knoten 0, besucht jede Liste jeden ihrer Knoten genau einmal und erreicht dann -1. Es gibt keinen Zyklus.
Entlang ihrer Verknüpfungen ist jede Liste in nicht absteigender Reihenfolge sortiert.

Beispiele

Eingabe: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Ausgabe: [1, 2, 3, 4, 6, 7, 9]
Erklärung: Wenn man den Verknüpfungen folgt, besucht die erste Liste die Knoten 0, 2, 1 und liest 1, 4, 6; die zweite liest 2, 3, 7, 9. Nimmt man jedes Mal das kleinere Element am Anfang, erhält man 1, 2, 3, 4, 6, 7, 9.

Eingabe: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Ausgabe: [-3, 0, 0, 5]
Erklärung: Die erste Liste lautet -3, 0, 5 und die zweite besteht aus dem einzelnen Wert 0. Beide 0 bleiben im Ergebnis, sodass es vier Werte enthält.

Eingabe: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Ausgabe: [1, 2, 3, 8, 10]
Erklärung: Die zweite Liste lautet 1, 2, 3, alle kleiner als die 8, mit der die erste Liste beginnt. Die gesamte zweite Liste kommt zuerst, dann 8, 10.

Weiterführende Frage

Kannst du k sortierte Listen in O(N log k) Zeit zusammenführen, wobei N die Gesamtzahl der Knoten ist?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Beide Listen sind sortiert, daher steht der kleinste verbleibende Wert immer am Anfang einer der beiden Listen. Vergleiche die beiden ersten Werte, verknüpfe den kleineren mit dem Ergebnis und gehe in dieser Liste einen Schritt weiter. Alle N = L1 + L2 Werte zu sortieren funktioniert ebenfalls, ignoriert aber diese Ordnung und kostet O(N log N).

Füge jeden Wert in ein Array ein und sortiere es

Idee

Die zusammengeführte Liste ist die sortierte Version aller N Werte. Kopiere also beide Wert-Arrays in eines und sortiere es. Die Reihenfolge der Knoten innerhalb der Arrays spielt keine Rolle, weil beim Sortieren jeder Wert an die richtige Stelle gesetzt wird. Bei N ≤ 4000 ist das schnell genug, aber ein Sortiervorgang benötigt O(N log N) Vergleiche, während ein Zusammenführen höchstens N-1 benötigt, und es greift nie auf einen Link zu – genau die Fähigkeit, die diese Aufgabe prüft.

Algorithmus

Kopiere values1 und values2 in ein Array.
Sortiere das Array in nicht absteigender Reihenfolge.
Gib es zurück.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Füge die Knoten hinter einem Dummy-Kopf ein

Idee

Ein Zeiger ist hier ein Knotenindex. Um die Knoten beider Listen zu einer Kette zu verbinden, nummerierst du sie durchgehend: Knoten j aus Liste 2 wird zu Knoten L1+j, und seine Verknüpfungen werden entsprechend verschoben. Ein Dummy-Knoten mit der Nummer L1+L2 steht vor dem Ergebnis.

Lass a und b auf den ersten noch nicht verwendeten Knoten jeder Liste und tail auf dem Ende der zusammengeführten Kette stehen. In jedem Schritt verknüpfst du tail mit dem kleineren vorderen Knoten und setzt diesen Zeiger sowie tail weiter. Wenn eine Liste aufgebraucht ist, ist der Rest der anderen bereits sortiert und verknüpft, sodass eine Zuweisung genügt, um ihn anzuhängen. Im ersten Beispiel wird Liste 2 zu den Knoten 3 bis 6. Nach den Knoten 0, 3, 6, 2, 1 ist Liste 1 leer, und link[tail] = 4 hängt 7, 9 an.

Jeder Knoten wird höchstens einmal verknüpft: Laufzeit O(N). Das gemeinsame Verknüpfungsarray benötigt O(N) Speicher, während Knotenobjekte keinen benötigen würden.

Algorithmus

Erstelle ein Link-Array: next1, dann next2, um L1 verschoben (-1 unverändert lassen), dann -1 für das Dummy-Element L1+L2. Erstelle die passenden Werte.
Setze a = 0, b = L1 und tail auf das Dummy-Element.
Solange weder a noch b -1 ist, verknüpfe tail mit dem kleineren Wert (bei Gleichstand a), rücke den entsprechenden Zeiger weiter und setze tail auf diesen.
Verknüpfe tail mit demjenigen von a und b, der nicht -1 ist.
Gehe von link[dummy] bis -1 und sammle die Werte.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Stolperfallen und Grenzfälle

Die Arrays in Indexreihenfolge zusammenführen. Die Knoten sind durcheinander gespeichert, daher ist values1 selbst nicht sortiert: Im ersten Beispiel ist es [1, 6, 4]. Nur der Durchlauf ab Knoten 0 ist sortiert.
Die übrigen Elemente vergessen. Wenn eine Liste zu Ende ist, wird die Schleife beendet. Werden die restlichen Elemente der anderen Liste verworfen, gehen die größten Werte verloren: 7, 9 im ersten Beispiel.
Den falschen Zeiger oder beide Zeiger weitersetzen. Nur die Liste, deren Knoten du übernommen hast, wird weitergesetzt.
Die beiden Nummerierungen vermischen. Knoten 2 von Liste 2 ist nicht Knoten 2 von Liste 1. Verschiebe die Indizes und Verknüpfungen von Liste 2 um L1 und belasse -1 unverändert.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität beim Zusammenführen zweier sortierter Listen?

Es ist O(L1 + L2): Bei jedem Vergleich wird ein Knoten platziert, und kein Knoten wird zweimal platziert. Bei Knotenobjekten benötigt das Zusammenführen O(1) zusätzlichen Speicher, da dabei nur Verknüpfungen geändert werden. Bei den hier verwendeten Arrays benötigt das gemeinsame Verknüpfungsarray O(L1 + L2) Speicher.

Warum einen Dummy-Knoten verwenden, wenn verkettete Listen zusammengeführt werden?

Ohne sie benötigt der erste Knoten des Ergebnisses einen separaten Code, weil es noch keinen Nachfolger gibt, an den er angehängt werden kann. Der Dummy ist ein Platzhalterkopf, sodass der erste Knoten genauso verknüpft wird wie alle anderen. Am Ende gibst du den Nachfolger des Dummys zurück, und der Platzhalter verschwindet.

Solltest du zwei sortierte Listen rekursiv oder iterativ zusammenführen?

Die rekursive Version ist kurz: Der kleinere Kopf wird mit dem Merge des Rests verknüpft. Aber sie verwendet einen Stack-Frame pro Knoten, sodass eine Liste mit ein paar tausend Knoten in manchen Sprachen den Stack überlaufen lassen kann. Die iterative Schleife mit einem Zeiger auf das Ende erledigt dieselbe Arbeit mit konstantem Stack-Speicherplatz.

def mergeTwoLists(next1, values1, next2, values2):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Erwartete Ausgabe

[1, 2, 3, 4, 6, 7, 9]