Führen Sie zwei sortierte verknüpfte Listen auf einfache und optimale Weise in Java zusammen

Das Zusammenführen zweier sortierter verknüpfter Listen ist ein häufiges Problem, das effizient gelöst werden kann. Hier erfahren Sie, wie Sie dies mit Java auf einfache und optimale Weise tun können.

Schritte:

1. Erstellen Sie einen Dummy-Knoten: Verwenden Sie einen Dummy-Knoten, um den Zusammenführungsprozess zu vereinfachen. Dieser Knoten dient als Anfang der zusammengeführten Liste.
2. Knoten vergleichen: Vergleichen Sie die aktuellen Knoten beider verknüpfter Listen. Hängen Sie den kleineren Knoten an die zusammengeführte Liste an und bewegen Sie den Zeiger dieser Liste nach vorne.
3. Verbleibende Knoten verarbeiten: Wenn eine Liste vor der anderen erschöpft ist, hängen Sie die verbleibenden Knoten der nicht erschöpften Liste an die zusammengeführte Liste an.
4. Gibt die zusammengeführte Liste zurück: Die zusammengeführte Liste beginnt beim Knoten neben dem Dummy-Knoten.

Java-Implementierung:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

Erläuterung:

1. ListNode-Klasse:

   • Stellt jeden Knoten in der verknüpften Liste mit einem ganzzahligen Wert (val) und einem Zeiger auf den nächsten Knoten (next) dar.

2. mergeTwoLists-Methode:

   • Dummy-Knoten: Ein Dummy-Knoten (Dummy) wird verwendet, um den Zusammenführungsprozess zu vereinfachen, indem er einen Ausgangspunkt bereitstellt.
   • Vergleichsschleife: Wir durchlaufen beide verknüpften Listen und vergleichen die aktuellen Knoten. Der kleinere Knoten wird zur zusammengeführten Liste hinzugefügt und wir wechseln zum nächsten Knoten in dieser Liste.
   • Verbleibende Knoten: Nachdem eine der Listen erschöpft ist, hängen wir den verbleibenden Teil der anderen Liste direkt an die zusammengeführte Liste an.
   • Zurück: Schließlich beginnt die zusammengeführte Liste beim Knoten neben dem Dummy-Knoten.

3. printList-Methode:

   • Diese Dienstprogrammfunktion druckt alle Knoten in der verknüpften Liste zur einfachen Visualisierung.

4. Hauptmethode:

   • Erstellen Sie zwei sortierte verknüpfte Listen: Zum Beispiel 1 -> 3 -> 5 und 2 -> 4 -> 6.
   • Listen zusammenführen: Die zusammengeführte Liste ist 1 -> 2 -> 3 -> 4 -> 5 -> 6.
   • Drucken Sie die Listen aus: Vor und nach dem Zusammenführen, um den Effekt zu sehen.

Komplexität:

• Zeitkomplexität: ( O(n + m) ), wobei ( n ) und ( m ) die Längen der beiden verknüpften Listen sind. Jeder Knoten in beiden Listen wird genau einmal verarbeitet.
• Raumkomplexität: ( O(1) ), da außer ein paar Hinweisen kein zusätzlicher Raum verwendet wird.

Diese Methode ist sowohl einfach als auch optimal zum Zusammenführen zweier sortierter verknüpfter Listen und sorgt so für effizienten und sauberen Code.

Das obige ist der detaillierte Inhalt vonFühren Sie zwei sortierte verknüpfte Listen auf einfache und optimale Weise in Java zusammen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!