Fusionar cadenas ordenadas
La misión
Problema
Recibes dos listas simplemente enlazadas, cada una ya ordenada en orden no decreciente. Únelas en una sola lista ordenada reenlazando los nodos existentes en lugar de crear nodos nuevos. Devuelve la cabeza de la lista fusionada, que queda vacía cuando las dos entradas están vacías.
Ejemplos
Input: a = 1 -> 4 -> 6, b = 2 -> 3
Output: 1 -> 2 -> 3 -> 4 -> 6
Input: a = empty, b = 7
Output: 7
Por qué: caso límite: un lado se agota antes de que empiece el bucle
Input: a = empty, b = empty
Output: empty
Por qué: caso límite: no hay nada que fusionar
Pistas
0 / 3
En cada momento solo dos candidatos pueden ir a continuación: el frente actual de cada cadena. El resto de ambas cadenas no importa hasta que una de ellas se consuma.
Hacer crecer una lista por el frente es incómodo, así que guarda un puntero al último nodo del resultado y engancha siempre detrás de él. Un nodo inicial descartable elimina el caso especial del primer enganche.
Compara una y otra vez los dos nodos del frente, separa el menor y cuélgalo de la cola del resultado. Cuando una cadena se vacíe, engancha toda la cadena restante de un solo paso, porque ya está ordenada.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(1)
Restricciones
- both lists are sorted in non-decreasing order
- either list may be empty
Solución
Las dos cadenas se consumen frente contra frente: siempre se toma la cabeza menor y se agrega a la cola del resultado. Un nodo ficticio (dummy node) al inicio hace que el primer agregado no necesite un trato especial, y la cabeza real es simplemente el nodo que le sigue. Cuando una cadena se agota, la otra ya está ordenada, así que el resto se engancha de una sola vez en lugar de nodo por nodo. El tiempo es O(n + m) y el espacio es O(1), ya que solo cambian punteros.
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def merge_sorted(a, b):
dummy = tail = Node(0) # starter node removes the empty-result case
while a and b:
if a.val <= b.val: tail.next, a = a, a.next
else: tail.next, b = b, b.next
tail = tail.next # the attached node is the new tail
tail.next = a or b # the leftover chain is already sorted
return dummy.next
print(dump(merge_sorted(build([1, 4, 6]), build([2, 3])))) # -> [1, 2, 3, 4, 6]
print(dump(merge_sorted(build([]), build([7])))) # -> [7]
print(dump(merge_sorted(build([]), build([])))) # -> []¿Lo que te frena es la idea y no el código? Fusionar dos listas ordenadas lo explica.