Fusionar dos listas ordenadas

Introducción
       
En este blog, te enseñaré cómo fusionar dos listas ordenadas en Java, Python, PHP, C++ y JavaScript.

En este artículo, vamos a ver lo siguiente:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

                       

Problema
Dadas dos listas enlazadas, combine ambas en una sola lista ordenada, y devuelva el puntero de inicio de la lista fusionada.

        
        
Pasos para realizar el ejercicio:
1.-Se crea un nuevo puntero: newHead, y será asignado a nodo con valor 0 o NULL. Este nodo se utilizará para almacenar la cabeza de la nueva lista ordenada.
        
2.- Se crea un puntero llamado nuevaLista. Este puntero se inicializará con el newHead, y será el encargado de unir los nodos.

3.- Se recorren ambas listas hasta que una se quede sin nodos.

Luego, se comparan los valores actuales de las dos listas, y el menor de estos será agregado a la nueva lista ordenada.

4.-Después se avanza a la siguiente posición del puntero con el nodo de menor valor evaluado.

5.- Posteriormente de agregar un nodo a la nueva lista ordenada, movemos el puntero de la nuevaLista a su siguiente posición.

6.- Una vez que una de las listas se quede sin nodos, se agregan todos los nodos restantes a la lista ordenada.

7.- Devolvemos la siguiente posición de newHead.

Presentación

Código en Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
 
        //paso #1
        ListNode newHead = new ListNode();
 
        //paso #2
        ListNode nuevaLista = newHead;
 
        //paso #3
        while (list1 != null && list2 != null) {
 
            if (list1.val < list2.val) {
                nuevaLista.next = list1;
                list1 = list1.next;  //paso #4
            } else {
                nuevaLista.next = list2;
                list2 = list2.next; //paso #4
            }
 
            //paso #5
            nuevaLista = nuevaLista.next;
        }
 
        //paso #6
        if (list1 != null) nuevaLista.next = list1;
        else nuevaLista.next = list2;
 
        //paso#7
        return newHead.next;
    }
}

Código en php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
 
    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        $newHead= new ListNode(0);
        $nuevaLista=$newHead;
 
        while($list1 && $list2){
            if($list1->val > $list2->val){
                $nuevaLista -> next = $list2;
                $list2= $list2->next;
            }
            else{
                $nuevaLista -> next = $list1;
                $list1= $list1->next;
            }
            $nuevaLista= $nuevaLista->next;
        }
 
        if($list1 && $list2==null)  $nuevaLista -> next= $list1;
        else                        $nuevaLista -> next= $list2;
 
        return $newHead->next;
 
    }
}

Código en Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        # Paso #1
        newHead = ListNode()
 
        # Paso #2
        nuevaLista = newHead
 
        # Paso #3
        while list1 and list2:
            if list1.val < list2.val:
                nuevaLista.next = list1
                list1 = list1.next  # Paso #4
            else:
                nuevaLista.next = list2
                list2 = list2.next  # Paso #4
 
            # Paso #5
            nuevaLista = nuevaLista.next
 
        # Paso #6
        nuevaLista.next = list1 or list2
 
        # Paso #7
        return newHead.next

Código en C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // Paso #1
        ListNode* newHead = new ListNode();
 
        // Paso #2
        ListNode* nuevaLista = newHead;
 
        // Paso 3#
        while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            nuevaLista->next = list1;
            list1 = list1->next;
        } else {
            nuevaLista->next = list2;
            list2 = list2->next;
        }
 
        // Avanzar al siguiente nodo de la nueva lista.
        nuevaLista = nuevaLista->next;
        }
 
        // Paso 6
        nuevaLista->next = list1 == nullptr ? list2 : list1;
 
        // Paso 7
        return newHead->next;
  }
};

Código en JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    // Paso #1
    const newHead = new ListNode();
 
    // Paso #2
    let nuevaLista = newHead;
 
    // Paso #3
    while (list1 !== null && list2 !== null) {
      if (list1.val < list2.val) {
        nuevaLista.next = list1;
        list1 = list1.next; // Paso #4
      } else {
        nuevaLista.next = list2;
        list2 = list2.next; // Paso #4
      }
 
      // Paso #5
      nuevaLista = nuevaLista.next;
    }
 
    // Paso #6
    nuevaLista.next = list1 !== null ? list1 : list2;
 
    // Paso #7
    return newHead.next;
};

        
    
Conclusión
En este blog, hemos visto cómo fusionar dos listas ordenadas en Java, Python, PHP, C++ y JavaScript.

Hemos visto ejemplos de código para cada método en cada lenguaje de programación.