So führen Sie geordnete verknüpfte Listen in Java zusammen

Problem

Fügen Sie zwei aufsteigend verknüpfte Listen zu einer neuen aufsteigend verknüpften Liste zusammen und kehren Sie zurück. Die neue verknüpfte Liste wird durch Verketten aller Knoten der beiden angegebenen verknüpften Listen gebildet.

Beispiel 1:

Eingabe: l1 = [1,2,4], l2 = [1,3,4]
Ausgabe: [1,1,2,3,4,4]

Beispiel 2:

8e99a69fbe029cd4e2b854e244eab143Eingabe: 128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143Ausgabe: 128dba7a3a77be0113eb0bea6ea0a5d0[]

Beispiel 3:

Eingabe: l1 = [], l2 = [0]
Ausgabe: [0]

Idee

Version 1

• Erstellen Sie eine leere verknüpfte Liste nList

• in beiden verknüpften Listen (l1, l2). Wenn Es ist nicht leer. Vergleichen Sie die Werte der ersten Elemente der beiden verknüpften Listen, nehmen Sie das kleinste heraus und fügen Sie es der neuen verknüpften Liste hinzu. Dann zeigt der Kopfzeiger der kleinen verknüpften Liste auf das nächste Bit und Der Zeiger von nList zeigt auch auf das nächste Bit.

• Wenn beide verknüpften Listen noch nicht leer sind, fahren Sie mit der Schleife fort.

• Wenn eine der beiden verknüpften Listen leer ist, verbinden Sie die nicht leere verknüpfte Liste mit die Rückseite von nList

• Schließlich die nächste von nList zurückgeben als Der Kopfknoten der neuen verknüpften Liste

Version 2

• ermittelt zunächst, ob die beiden verknüpften Listen leer sind, und gibt die leere verknüpfte Liste direkt zurück wenn es leer ist. Wenn es nicht leer ist, gehen Sie weiter nach unten

• , um zu bestimmen, welcher der Kopfknoten von l1 und l2 kleiner ist, und speichern Sie diesen Knoten dann als Kopfknoten. Die nachfolgenden Knoten werden über diesem Knoten gespleißt auf einmal.

• Die folgenden Ideen sind die gleichen wie Version eins

Antwort

Version eins

Erstellen Sie einen neuen Knoten und übertragen Sie alle ursprünglich verknüpften Listen in die neue verknüpfte Liste

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

Version zwei

Wählen Sie eine aus die ursprüngliche verknüpfte Liste integrieren und keinen neuen Speicher anwenden

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 == null ? list2 : list1;
    }
    ListNode head = list1.val <= list2.val ? list1 : list2;
    if (list1.val <= list2.val)
        list1 = list1.next;
    else
        list2 = list2.next;
    ListNode tmp = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        tmp.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        tmp = tmp.next;
    }
    tmp.next = list1 != null ? list1 : list2;
    return head;
}

Das obige ist der detaillierte Inhalt vonSo führen Sie geordnete verknüpfte Listen in Java zusammen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!