Mesclar K Listas Ordenadas: Soluções com Heap e Divisão e Conquista em Python

Mesclar k Listas Ordenadas (LeetCode 23) pede que você mescle k listas encadeadas ordenadas em uma única lista ordenada. É um problema popular porque a solução de força bruta é óbvia, e a parte interessante é escolher entre duas boas formas de fazer melhor: um min-heap ou divisão e conquista. Ambas rodam em O(N log k), onde N é o número total de nós.

O problema

Dado um array de k listas encadeadas, cada uma ordenada em ordem crescente, mescle todas em uma única lista encadeada ordenada e retorne-a.

Exemplo: [[1,4,5],[1,3,4],[2,6]] se torna [1,1,2,3,4,4,5,6].

Perguntas para fazer ao entrevistador:

• O array pode estar vazio, ou conter listas vazias? (Sim, trate os dois casos.)
• Devo reutilizar os nós existentes ou criar novos? (Reutilizar é ok e economiza memória.)
• Valores duplicados são possíveis? (Sim, então mantenha a mesclagem estável se isso importar.)

Força bruta

Junte todos os valores em um array, ordene-o e reconstrua uma lista. O tempo é O(N log N) e o espaço é O(N). Funciona, mas ignora que cada lista já está ordenada, então raramente é aceito como resposta final.

Abordagem 1: um min-heap

Mantenha um ponteiro por lista. O próximo nó na saída é sempre o menor entre os cabeças atuais, então mantenha os cabeças em um min-heap.

1. Insira o cabeça de cada lista não vazia no heap.
2. Remova o menor, anexe-o ao resultado e insira seu próximo nó, se houver.
3. Repita até o heap ficar vazio.

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

O índice i é um critério de desempate. Sem ele, duas entradas com valores iguais fariam o Python comparar objetos ListNode, o que gera um TypeError.

Complexidade: cada um dos N nós entra no heap uma vez e sai uma vez, e cada operação custa O(log k), então o tempo é O(N log k). O heap contém no máximo k nós, então o espaço extra é O(k).

Abordagem 2: divisão e conquista

Mesclar duas listas ordenadas é fácil e leva tempo O(n). Mescle as listas em pares, depois mescle os resultados em pares, e assim por diante, como um torneio.

def merge_two(a, b):
    dummy = tail = ListNode()
    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
    tail.next = a or b
    return dummy.next

def merge_k_lists_dc(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            other = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(lists[i], other))
        lists = merged
    return lists[0]

Complexidade: há cerca de log k rodadas, e cada rodada percorre todos os N nós uma vez, então o tempo é O(N log k). A versão com loop precisa de apenas O(1) de espaço extra além da lista de cabeças.

Por que não mesclar uma a uma?

Mesclar a lista 1 com a lista 2, depois o resultado com a lista 3, e assim por diante, parece natural, mas custa mais. A primeira lista é copiada através de k mesclagens. Se cada lista tem n nós, o trabalho total é cerca de n x (1 + 2 + ... + k), que é O(n k ao quadrado). Emparelhar as listas mantém os tamanhos equilibrados, então cada nó é percorrido cerca de log k vezes.

Comparando as duas

Se um entrevistador disser que as listas são grandes demais para a memória e chegam como streams, a abordagem com heap se estende naturalmente, já que só precisa do cabeça atual de cada stream.

Casos extremos para testar

Como explicar em uma entrevista

1. Declare a força bruta e por que ela é desperdício.
2. Diga a observação-chave: o próximo nó da saída é o menor cabeça atual.
3. Escolha o heap, escreva-o e mencione o critério de desempate.
4. Declare a complexidade: tempo O(N log k) e espaço O(k).
5. Ofereça divisão e conquista como a alternativa com espaço O(1).
6. Teste com uma entrada vazia e uma com duplicatas.

Testei as duas versões acima contra uma verificação baseada em ordenação em 3.000 entradas aleatórias, incluindo listas vazias, antes de publicar. Fazer uma verificação aleatória rápida como essa é um bom hábito quando você pratica.

Prática relacionada

Se isso foi fácil, tente Merge Two Sorted Lists primeiro, depois Sort List e Find Median from Data Stream, que usam as mesmas ideias. Veja nosso Big O cheat sheet para os termos de complexidade, o guia de longest common substring para programação dinâmica, e o guia de assistente para entrevista de programação para saber como praticar.

Fale sobre sua abordagem em voz alta enquanto programa. Uma transcrição de entrevista simulada mostra se você explicou a observação-chave antes de escrever. Siga as regras do empregador sobre ferramentas de IA em qualquer avaliação ao vivo.