Saltar al contenido

Fusionar cadenas ordenadas

Fácil#two-pointers#dummy-node~20 min

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

Tiempo objetivo
O(n + m)
Espacio objetivo
O(1)

Restricciones

  • both lists are sorted in non-decreasing order
  • either list may be empty

¿Lo que te frena es la idea y no el código? Fusionar dos listas ordenadas lo explica.

Python 3Ctrl+Enter ejecuta