Fusionner deux listes chaînées triées en Java de manière simple et optimale

La fusion de deux listes chaînées triées est un problème courant qui peut être résolu efficacement. Voici comment le faire de manière simple et optimale en utilisant Java.

Mesures:

1. Créer un nœud factice : utilisez un nœud factice pour simplifier le processus de fusion. Ce nœud servira de début à la liste fusionnée.
2. Comparer les nœuds : comparez les nœuds actuels des deux listes chaînées. Attachez le plus petit nœud à la liste fusionnée et déplacez le pointeur de cette liste vers l'avant.
3. Gérer les nœuds restants : Si une liste est épuisée avant l'autre, attachez les nœuds restants de la liste non épuisée à la liste fusionnée.
4. Renvoyer la liste fusionnée : La liste fusionnée commence à partir du nœud situé à côté du nœud factice.

Implémentation Java :

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);
    }
}

Explication:

1. Classe ListNode :

   • Représente chaque nœud de la liste chaînée avec une valeur entière (val) et un pointeur vers le nœud suivant (next).

2. Méthode mergeTwoLists :

   • Nœud factice : Un nœud factice (factice) est utilisé pour simplifier le processus de fusion en fournissant un point de départ.
   • Boucle de comparaison : Nous parcourons les deux listes chaînées, en comparant les nœuds actuels. Le nœud le plus petit est ajouté à la liste fusionnée et nous passons au nœud suivant dans cette liste.
   • Nœuds restants : Une fois l'une des listes épuisée, nous attachons la partie restante de l'autre liste directement à la liste fusionnée.
   • Retour : Enfin, la liste fusionnée commence à partir du nœud à côté du nœud factice.

3. Méthode printList :

   • Cette fonction utilitaire imprime tous les nœuds de la liste chaînée pour une visualisation facile.

4. Méthode principale :

   • Créez deux listes chaînées triées : Par exemple, 1 -> 3 -> 5 et 2 -> 4 -> 6.
   • Fusionner les listes : La liste fusionnée sera 1 -> 2 -> 3 -> 4 -> 5 -> 6.
   • Imprimez les listes : Avant et après la fusion pour voir l'effet.

Complexité:

• Complexité temporelle : ( O(n + m) ), où ( n ) et ( m ) sont les longueurs des deux listes chaînées. Chaque nœud des deux listes est traité exactement une fois.
• Complexité spatiale : ( O(1) ), car aucun espace supplémentaire n'est utilisé en dehors de quelques pointeurs.

Cette méthode est à la fois simple et optimale pour fusionner deux listes chaînées triées, garantissant un code efficace et propre.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!