Entrevista técnica: ¿Cómo fusionar K listas enlazadas ordenadas?

Planteamiento y contexto aplicable

Dado un arreglo lists que contiene las cabezas de k listas simplemente enlazadas, fusiona cada nodo en una sola lista cuyos valores estén en orden no decreciente. Cualquier lista de entrada puede estar vacía, los valores pueden ser negativos o estar duplicados, y el número total de nodos entre todas las entradas es N.

Asume que cada entrada es acíclica, ya está ordenada y no comparte ningún nodo con otra entrada. La implementación puede reenlazar los nodos existentes y no debe asignar un nodo de reemplazo para cada valor. Los valores iguales no tienen un orden requerido entre diferentes listas de entrada. Retorna None cuando el arreglo esté vacío o cada cabeza sea None. Apunta a un tiempo de O(N log k) y un espacio auxiliar de O(k).

Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Este es un problema de listas enlazadas, por lo que la propiedad de los punteros es parte del contrato. Si quien invoca requiere que todas las listas de entrada permanezcan sin cambios, la elección algorítmica puede seguir siendo la misma, pero la salida debe asignar N nuevos nodos y su espacio de salida pasa a ser O(N).

Qué evalúa el entrevistador

La primera señal es si el candidato aprovecha la estructura ordenada. Aplanar todos los valores y ordenarlos funciona, pero consume un tiempo de O(N log N) y un almacenamiento adicional de O(N). Escanear todas las cabezas actuales para cada nodo de salida utiliza la propiedad de orden pero cuesta O(Nk). Una respuesta sólida indaga qué conjunto pequeño puede contener el siguiente mínimo global.

La segunda señal es el invariante de frontera. Para cada lista no agotada, solo su primer nodo no fusionado puede ser la siguiente salida. Cada nodo más profundo es al menos tan grande porque esa lista está ordenada. Por lo tanto, un min-heap que mantiene un nodo de frontera por cada lista no agotada reduce el escaneo de hasta k candidatos a una extracción e inserción del mínimo sobre un heap de tamaño a lo sumo k.

La tercera señal es la demostración y la contabilidad de costos. La respuesta debe indicar por qué el nodo seleccionado es globalmente mínimo, por qué insertar únicamente su sucesor restaura el invariante, por qué cada nodo se emite exactamente una vez y por qué el heap nunca excede el número de listas no vacías. Decir "usa una cola de prioridad" sin ese argumento deja sin formular el razonamiento central.

La cuarta señal es la disciplina de implementación. En Python, los elementos del heap con prioridades numéricas iguales no deben recurrir a la comparación de objetos ListNode. Un número de secuencia único sirve para desempatar. Cuando se reutilizan los nodos, el código guarda el sucesor original antes de desvincular y anexar el nodo, de modo que el prefijo construido tenga un único dueño claro y no conserve un puntero temporal hacia una lista no fusionada.

La señal final es la elección entre dos enfoques óptimos. Un min-heap y la fusión balanceada por pares logran ambos un tiempo de O(N log k). El heap hace explícita la frontera y se extiende de forma natural a iteradores o flujos (streams). Divide y vencerás utiliza la fusión ordinaria de dos listas y puede emplear un espacio de trabajo de punteros constante más allá del arreglo de cabezas. El contrato de entrada decide qué explicación es más simple.

Preguntas para aclarar antes de responder

• ¿Puedo mutar y reutilizar los nodos de entrada? Si es así, reenlázalos y usa únicamente O(k) de almacenamiento en el heap. Si no,

asigna la salida y reporta su espacio O(N) por separado del estado auxiliar del algoritmo.

• ¿Todas las entradas están ordenadas y son acíclicas? El algoritmo planteado depende de ambas cosas. Validar el orden cuesta

O(N); detectar ciclos también cambia el trabajo y no debería agregarse silenciosamente a la solución base.

• ¿Qué cuenta k? Sea m el número de listas no vacías. El heap contiene como máximo m, por lo que un

límite más preciso es O(N log m) para m >= 2, con trabajo lineal para cero o una lista no vacía.

• ¿Los valores iguales deben preservar un orden entre listas? La pregunta base solo requiere valores ordenados. Un

contrato estable necesita un orden de origen definido codificado en la clave del heap.

• ¿Puedo usar la cola de prioridad del lenguaje? Por lo general sí, a menos que el entrevistador esté evaluando por separado

la implementación del heap. Aclara esto antes de gastar tiempo de la entrevista escribiendo un binary heap desde cero.

• ¿Son estas listas enlazadas totalmente materializadas o iteradores perezosos (lazy)? Un heap maneja ambos, pero una versión

con iteradores debe evitar avanzar una fuente hasta que su valor actual haya sido extraído.

• ¿Qué debería pasar con el arreglo de cabezas de entrada? El código a continuación deja las entradas del arreglo intactas pero

reconfigura sus nodos. Si quien invoca observa ambos, documenta esa transferencia de propiedad.

Estructura de respuesta en 30 segundos

"Dado que solo el primer nodo no fusionado de cada lista ordenada puede ser el siguiente mínimo global, mantendré esos nodos de frontera en un min-heap. Extraigo el nodo más pequeño, lo anexo al resultado y luego inserto solo su sucesor guardado. El invariante es que el heap contiene exactamente una frontera de cada lista no agotada; por lo tanto, el nodo extraído es seguro y restaurar su frontera de origen preserva el invariante. Cada uno de los N nodos se extrae una vez y se inserta a lo sumo un sucesor, con un tamaño de heap de como máximo k, lo que da un tiempo de O(N log k) y un espacio auxiliar de O(k). Reutilizaré los nodos, agregaré un desempate único para que los valores iguales nunca comparen objetos de nodo, y probaré entradas vacías, duplicados, negativos, longitudes desiguales y una sola lista. La fusión balanceada por pares es la alternativa principal con el mismo límite de tiempo."

Análisis detallado paso a paso

Comienza con las alternativas directas e identifica el trabajo repetido:

Es fácil subestimar la fusión secuencial. Si las k listas tienen una longitud similar L, el trabajo crece como 2L + 3L + ... + kL, lo cual es O(Lk²). Dado que N = Lk, eso es O(Nk). La fusión por pares evita el acumulador desbalanceado combinando listas en rondas, de modo que cada nodo participa a lo sumo en ceil(log₂ k) niveles de fusión.

Para la solución con heap, mantén este invariante antes de cada extracción:

For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

La inicialización inserta cada cabeza no vacía, por lo que el invariante se cumple. Supongamos que se cumple al inicio de una iteración. Cualquier nodo no fusionado es una frontera en el heap o aparece después de la frontera de su lista. Dado que cada entrada está ordenada, un nodo más profundo no puede ser menor que esa frontera. Por lo tanto, el elemento mínimo del heap no es mayor que ningún nodo no fusionado y puede anexarse con seguridad.

Tras remover un nodo, solo su lista de origen pierde su representante. Guarda el sucesor original de ese nodo, desvincula el nodo, anéxalo e inserta el sucesor cuando exista. Todas las demás fronteras de origen siguen siendo válidas, por lo que el invariante se restaura. Cada iteración emite un nodo; después de exactamente N iteraciones, cada lista se agota y el heap queda vacío. Esto demuestra el ordenamiento, la completitud y la terminación.

La siguiente implementación en Python utiliza un número de secuencia monótonamente creciente como el segundo campo de la tupla. Ese número es único, por lo que los valores iguales nunca hacen que la comparación de tuplas alcance el objeto de nodo no ordenable.

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

Hay m inserciones iniciales, donde m <= k es el número de listas no vacías. Cada nodo se extrae una vez, y cada nodo excepto una cola final puede provocar una inserción. Las operaciones de heap cuestan O(log m) mientras el heap tiene como máximo m elementos. Para m >= 2, el tiempo total es O(N log m), convencionalmente expresado como O(N log k); para m <= 1, el recorrido es O(N). El heap, el contador de secuencia, el nodo dummy y los punteros usan un espacio auxiliar de O(m). Los nodos retornados son los nodos originales, por lo que son salida y no nuevo almacenamiento algorítmico.

Desvincular node.next no es necesario para encontrar el sucesor porque se guardó primero. Hace que la propiedad sea explícita: el prefijo fusionado nunca apunta temporalmente hacia una lista de origen que aún no ha ganado en el heap. El siguiente anexo asigna el sucesor de la cola. El algoritmo nunca cambia un valor y nunca inserta el mismo nodo dos veces bajo el contrato de entradas acíclicas y disjuntas.

Ejecuta pruebas que apunten a la estructura, no solo a un arreglo de caso feliz:

def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

Para una validación de nivel de producción, registra también las identidades de todos los nodos de entrada, recorre la salida con un conjunto de visitados y demuestra tres propiedades: ausencia de ciclos, exactamente N identidades de nodo únicas y valores no decrecientes. Esto detecta inserciones duplicadas, pérdida de nodos y ciclos de punteros que una aserción basada únicamente en valores puede pasar por alto.

Elige la fusión balanceada por pares cuando el entrevistador busque manipulación de punteros, una cola de prioridad no esté disponible o minimizar el almacenamiento del heap sea relevante. Elige el heap cuando las fuentes se expongan como iteradores, cuando el número de fuentes activas cambie o cuando hacer explícito el mecanismo del "siguiente candidato global" mejore la claridad. Ambos son enfoques óptimos válidos bajo el contrato base; explica el motivo de la elección.

Respuesta de muestra de alta calidad

"Reutilizaré los nodos de entrada y asumiré que cada lista está ordenada, es acíclica y es disjunta. Sea N el total de nodos y m las listas no vacías. La siguiente salida solo puede ser una de las m cabezas actuales: cualquier nodo más profundo es al menos tan grande como su cabeza. Por lo tanto, pondré una cabeza por cada lista no vacía en un min-heap.

Mi invariante es que el heap contiene exactamente el primer nodo no fusionado de cada lista no agotada y la salida contiene cada nodo extraído una vez en orden ascendente. Extraigo el mínimo, guardo y desvinculo su sucesor, anexo el nodo e inserto ese sucesor. El nodo extraído es globalmente seguro porque cualquier otro nodo no fusionado está detrás de una frontera del heap que no es menor. Insertar el sucesor restaura el invariante de una frontera por lista.

En Python, los elementos son (value, sequence, node). El valor de secuencia único evita que las prioridades iguales intenten comparar objetos de nodo; no garantiza un orden estable entre listas porque el planteamiento no lo requiere. Cada nodo se extrae una vez y se inserta a lo sumo una vez, con un máximo de m elementos en el heap. Eso representa O(N log m), normalmente escrito como O(N log k), y un espacio auxiliar de O(m); cero o una lista no vacía es lineal.

Probaría un arreglo vacío, listas todas vacías, una sola lista, longitudes desiguales, negativos y valores iguales. También verificaría las identidades de los nodos y la ausencia de ciclos porque la solución reconfigura punteros. La fusión balanceada por pares es la alternativa principal: también cuesta O(N log k) y utiliza únicamente la primitiva de fusión de dos listas, por lo que la preferiría si el ejercicio enfatiza el código de punteros o prohíbe un heap de biblioteca."

Errores comunes

• Aplanar y ordenar de inmediato → la solución ignora que las entradas están ordenadas y gasta O(N log N) más

almacenamiento de salida → Mantén una frontera por cada fuente ordenada.

• Escanear todas las k cabezas para cada nodo → la selección del mínimo pasa a ser O(Nk) → **Usa un min-heap de tamaño k o

fusión balanceada por pares.**

• Fusionar una lista repetidamente en un resultado creciente → los primeros nodos se recorren a lo largo de muchas

fusiones posteriores → Combina las listas en rondas balanceadas.

• Insertar todos los nodos en el heap → el tamaño del heap crece a N, produciendo un trabajo de O(N log N) → **Inserta solo

un nodo actual de cada fuente.**

• Almacenar (value, node) en un heap de Python → los valores iguales intentan comparar objetos de nodo no ordenables →

Agrega un desempate numérico único.

• Avanzar una fuente antes de guardar su sucesor → la reconfiguración de punteros puede perder el resto de la lista →

Guarda primero el sucesor, luego desvincula y anexa.

• Afirmar un espacio de O(1) porque los nodos se reutilizan → el heap aún mantiene hasta k elementos → **Separa

la asignación de salida del estado auxiliar.**

• Validar únicamente los valores de salida → un ciclo, un nodo duplicado o un nodo perdido pueden pasar desapercibidos → **Verifica

las identidades de los nodos, la cantidad, el orden y la ausencia de ciclos.**

• Agregar validación de orden y ciclos sin aclarar → la implementación resuelve un contrato más amplio

y cambia el costo → Declara las suposiciones y agrega validación solo cuando se solicite.

Preguntas de seguimiento y respuestas

¿Por qué el mínimo del heap es el siguiente mínimo global?

Cada lista ordenada no agotada aporta su primer nodo no fusionado. Cualquier otro nodo está detrás de una de estas fronteras y no puede ser menor que ella. Por lo tanto, la frontera más pequeña no es mayor que ningún nodo no fusionado. Extraerla es seguro, e insertar su sucesor restaura la cobertura de esa fuente.

¿Qué cambia si los valores iguales deben ser estables según el orden de las listas de entrada?

Define la estabilidad con precisión y luego usa una clave de heap compuesta, como el valor seguido del índice de la lista de origen. Dado que solo un nodo por fuente está presente, el índice de origen resuelve los empates entre listas mientras que el orden propio de cada lista se preserva naturalmente. El desempate por secuencia base garantiza la comparabilidad, no esa política más estricta.

¿Cuándo es mejor divide y vencerás que un heap?

Usa la fusión balanceada por pares cuando la fusión de dos listas ya esté disponible, la entrevista enfatice la manipulación de punteros o no se disponga de una cola de prioridad. Cada ronda toca cada nodo restante una vez y hay O(log k) rondas. Un heap es más claro para fuentes perezosas (lazy) y cantidades variables de fuentes activas.

¿Qué pasa si las listas de entrada deben permanecer sin cambios?

Mantén la misma lógica de selección pero asigna un nuevo nodo para cada valor extraído. El tiempo se mantiene en O(N log k). El estado auxiliar de selección sigue siendo O(k), mientras que la asignación de salida requerida es O(N). Declara ambas en lugar de ocultar la memoria de salida dentro de la afirmación de espacio.

¿Qué pasa si hay diez mil posiciones de listas pero solo cinco no están vacías?

La inicialización escanea las k posiciones una vez, y luego el heap contiene como máximo m = 5 elementos. El tiempo preciso es O(k + N log m) y el espacio auxiliar es O(m). Reportar únicamente O(N log k) es seguro como cota superior, pero oculta el beneficio de omitir cabezas vacías.

¿Cómo fusionarías iteradores ordenados en lugar de listas enlazadas?

Lee un valor de cada iterador no vacío en el heap junto con la identidad de su fuente. Después de emitir el mínimo, avanza solo esa fuente e inserta su siguiente valor. La demostración de la frontera no cambia, el resultado puede ser perezoso (lazy) y la memoria permanece proporcional a las fuentes activas en lugar del total de valores.

¿Puede el código usar heapreplace tras extraer un nodo con sucesor?

No después de un heappop separado, porque la raíz anterior ya ha salido del heap. Una implementación podría mirar (peek), guardar la fuente de la raíz y reemplazar la raíz en una sola operación cuando esa fuente tenga un sucesor, pero la rama para una fuente agotada se mantiene. El código más simple de extracción y posterior inserción es más fácil de demostrar en una entrevista y tiene el mismo límite asintótico.

¿Cómo probarías la corrección de punteros más allá de los ejemplos?

Captura la identidad de cada nodo de entrada antes de fusionar. Recorre el resultado rechazando identidades repetidas, cuenta exactamente N nodos, verifica cada valor adyacente y confirma que el conjunto de identidades coincida. Genera listas ordenadas aleatoriamente y compara los valores con un oráculo confiable de aplanar y ordenar; el oráculo verifica la prueba, no la complejidad de producción.