Sortierte Listen zusammenführen

Heute schauen wir uns eine weitere verknüpfte Listenaufgabe an.

Erstellen Sie eine Funktion zum Zusammenführen von zwei sortierten verknüpften Listen. Die resultierende Liste sollte eine sortierte Liste sein, die die Knoten der beiden Listen verwendet.

Dazu verwenden wir die generische Linked-List-Implementierung aus dem vorherigen Beitrag, die hier zu finden ist

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

Die Logik ist ziemlich einfach zu befolgen. Zuerst richten wir Zeiger auf die Köpfe der beiden Listen und die resultierende Liste ein. Da wir den „Kopf“ der resultierenden Liste nicht kennen, erstellen wir einen Dummy-Knoten als Platzhalter (wir werden diesen später korrigieren). Wir erstellen außerdem einen aktuellen Knoten, rp, für die Ergebnisliste.

Als nächstes durchlaufen wir die beiden Listen. Wir haben für jede Liste einen aktuellen Knoten. Bei jedem Schritt prüfen wir, welcher der beiden aktuellen Knoten den kleineren Wert hat, und setzen diesen Knoten auf die Ergebnisliste. Verschieben Sie dann den aktuellen Knoten dieser Liste (den kleineren) zum nächsten Knoten in der Liste. Außerdem müssen wir den aktuellen Knoten des Ergebnisses an die nächste Stelle verschieben.

Unsere Schleifenlogik besteht einfach darin, dies so lange zu tun, bis wir das Ende einer der Listen erreichen. Zu diesem Zeitpunkt wissen wir, dass für eine der Listen keine weiteren Elemente zum Vergleich vorhanden sind. sie sind bereits in der Ergebnisliste. Daher können wir die verbleibenden Knoten der anderen Liste dann einfach an das Ende des Ergebnisses setzen, da wir wissen, dass sie bereits sortiert sind.

Wie würden Sie das anders machen? Können wir das optimieren? Lass es mich in den Kommentaren wissen.

Danke!

Den Code für diesen Beitrag und alle Beiträge dieser Reihe finden Sie hier

Das obige ist der detaillierte Inhalt vonSortierte Listen zusammenführen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!