Comment fusionner des listes chaînées ordonnées en Java

Problème

Fusionner deux listes chaînées ascendantes en une nouvelle liste chaînée ascendante et revenir. La nouvelle liste chaînée est formée en concaténant tous les nœuds des deux listes chaînées données.

Exemple 1 :

Entrée : l1 = [1,2,4], l2 = [1,3,4]
Sortie : [1,1,2,3,4,4]

Exemple 2 :

Entrée : l1 = [], l2 = []
Sortie : []

Exemple 3 :

Entrée : l1 = [], l2 = [0]
Sortie : [0]

Idée

Version 1

• Créer une liste chaînée vide nList

• Dans les deux listes chaînées (l1, l2) Si il n'est pas vide, comparez les valeurs des premiers éléments des deux listes chaînées, retirez le plus petit et ajoutez-le à la nouvelle liste chaînée. Ensuite, le pointeur de tête de la petite liste chaînée pointe vers le bit suivant, et. le pointeur de nList pointe également vers le bit suivant

• Si les deux listes chaînées ne sont pas encore vides, continuez à boucler

• Si l'une des deux listes chaînées est vide, collez la liste chaînée non vide à l'arrière de nList

• Enfin, renvoie le suivant de nList en tant que nœud principal de la nouvelle liste chaînée

Version 2

• détermine d'abord si les deux listes chaînées sont vides et renvoie directement la liste chaînée vide s'il est vide. S'il n'est pas vide, continuez à descendre

• pour déterminer lequel des nœuds principaux de l1 et l2 est le plus petit, puis enregistrez ce nœud comme nœud principal, et les nœuds suivants seront épissés par-dessus. nœud à la fois.

• Les idées suivantes sont les mêmes que la première version

Réponse

Version un

Créez un nouveau nœud et transférez toutes les listes chaînées d'origine vers la nouvelle liste chaînée

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 deux

Sélectionnez-en une parmi la liste chaînée d'origine Intégrez et n'appliquez aucune nouvelle mémoire

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

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!