Padrão 4: Merge de listas ordenadas

Juntar duas listas ordenadas numa só, também ordenada, é uma operação fundamental — e a peça central do merge sort. Em listas ligadas ela é especialmente elegante: você não copia nada, só costura os ponteiros.

🎯

Tente primeiro: Merge Two Sorted Lists

Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.

Dadas duas listas ligadas ordenadas l1 e l2, junte-as numa só lista ordenada e retorne a cabeça.

Exemplo: 1 → 2 → 4 e 1 → 3 → 4 → 1 → 1 → 2 → 3 → 4 → 4.

Carregando editor…

Tentou? Dá para jogar tudo num array, ordenar e reconstruir — mas isso ignora que as listas já estão ordenadas e gasta memória. A teoria abaixo costura as duas em uma passada, com O(1) de espaço.

A teoria: costurar com um dummy guiando

Como as duas listas já estão ordenadas, o menor próximo elemento do resultado é sempre a cabeça de uma das duas. Então o algoritmo é: compare as cabeças, pegue a menor, avance aquela lista, repita.

O ponto delicado é montar o resultado sem casos especiais para o primeiro nó — e aqui o dummy node (aula 2) brilha de novo:

dummy → (vazio)
cauda = dummy
enquanto l1 e l2 existem:
    se l1.val <= l2.val: cauda.next = l1; avança l1
    senão:               cauda.next = l2; avança l2
    avança cauda
cauda.next = o que sobrou (l1 ou l2)   ← uma das listas acaba antes
retorna dummy.next

O dummy segura o início; a cauda é onde você vai "pendurando" o próximo menor nó. No fim, uma das listas esvazia e a outra (cujo resto já está ordenado) é anexada de uma vez.

Carregando editor…

Por que é O(n + m) tempo e O(1) espaço?

Cada nó das duas listas é visitado uma vez ao ser costurado no resultado — total O(n + m), onde n e m são os tamanhos. Não criamos nós novos nem arrays: apenas religamos os next dos nós que já existem, com um dummy e um ponteiro de cauda → O(1) de espaço. (Note que <=, em vez de <, mantém a ordem relativa de valores iguais — uma propriedade "estável", útil quando importa.)

Subindo de nível: Merge k Sorted Lists

E se forem k listas ordenadas para juntar? Duas estratégias famosas, ambas usando o merge de duas como peça:

Merge em par, em torneio: junte as listas duas a duas, depois os resultados duas a duas, e assim por diante (como um campeonato mata-mata). São log k "rodadas", cada uma processando todos os N elementos → O(N log k).
Min-heap: mantenha as k cabeças num heap e retire sempre a menor — você vai ver isso na seção Heap, onde este problema reaparece.

O recado: o merge de duas listas não é só um exercício — é um bloco de construção que escala para problemas bem maiores.

🧠 Quiz de fixação

0/4

1. Por que o merge de duas listas ordenadas não precisa de um passo de ordenação?

2. Qual o papel do nó dummy no merge?

3. Depois que uma das listas esvazia, por que basta fazer cauda.next = (a outra)?

4. Qual a complexidade de juntar k listas com a estratégia de torneio (par a par)?

Resumo

Merge de duas listas ordenadas: compare as cabeças, costure a menor, avance; um dummy guia e o resto é anexado no fim.
O(n + m) tempo, O(1) espaço — só religa ponteiros, não copia.
É bloco de construção do merge k listas (torneio O(N log k) ou heap).

Próxima aula: juntar tudo — problemas difíceis que combinam meio, reversão e merge.

Todas as aulas da seção