Padrão 5: Combinando os padrões
Os problemas "difíceis" de lista ligada raramente trazem uma ideia nova — eles encaixam os padrões que você já domina. Esta aula mostra como compor meio + reversão + merge para resolver algo que, de cara, parece assustador.
Tente primeiro: Reorder List
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.
Reordene a lista L0 → L1 → ... → Ln-1 → Ln para L0 → Ln → L1 → Ln-1 → L2 → ... (intercala do começo e do fim), no lugar. Retorne a cabeça.
Exemplo: 1 → 2 → 3 → 4 → 1 → 4 → 2 → 3. 1 → 2 → 3 → 4 → 5 → 1 → 5 → 2 → 4 → 3.
Tentou? Sem um plano, reordenar
L0 → Ln → L1 → Ln-1 → ...no lugar parece caótico. A teoria abaixo mostra que é só três peças conhecidas em sequência.
A teoria: decompor em sub-problemas conhecidos
O Reorder List pede transformar L0 → L1 → ... → Ln em
L0 → Ln → L1 → Ln-1 → ... — intercalando a primeira metade com a segunda
metade invertida. Em vez de atacar de uma vez, decomponha:
- Ache o meio da lista → padrão lento/rápido (aula 4).
- Reverta a segunda metade → padrão reversão in-place (aula 3).
- Intercale as duas metades, alternando um nó de cada → costura de ponteiros (como no merge, aula 5).
Cada peça é O(n) e O(1), feita uma após a outra — então o todo é O(n) de tempo e O(1) de espaço. O "difícil" virou três "fáceis" em sequência.
1 → 2 → 3 → 4 → 5
(1) meio: primeira [1,2,3] | segunda [4,5]
(2) reverte 2ª: primeira [1,2,3] | segunda [5,4]
(3) intercala: 1 → 5 → 2 → 4 → 3
A estratégia geral: decompor
Quando um problema de lista parecer grande demais, pergunte: que peças conhecidas o compõem? Vários "difíceis" se desmontam assim:
| Problema | Peças que ele combina |
|---|---|
| Reorder List | meio + reversão + intercalar |
| Palindrome Linked List | meio + reversão (da 2ª metade) + comparação |
| Sort List (merge sort) | meio (dividir) + merge + recursão |
| Reverse Nodes in k-Group | reversão (em blocos de k) + contagem |
Repare: nenhum exige uma ideia inédita. O que separa quem trava de quem resolve é ter os padrões automatizados e enxergar a decomposição. Por isso investimos tanto em cada peça nas aulas anteriores.
🧠 Quiz de fixação
0/41. Qual é a estratégia central para problemas 'difíceis' de lista ligada?
2. No Reorder List, por que fazer slow.next = None depois de achar o meio?
3. Por que o Reorder List é O(n) de tempo e O(1) de espaço?
4. 'Verificar se uma lista é palíndromo em O(1) de espaço' decompõe em quais padrões?
Resumo
- Problemas difíceis de lista = combinação dos padrões básicos, não ideias novas.
- Reorder List = meio (lento/rápido) + reverter 2ª metade + intercalar; cada peça O(n)/O(1), logo o todo é O(n)/O(1).
- A habilidade-chave é decompor: "que peças conhecidas formam isto?".
Última parada: a síntese da seção e o quiz antes da prova final.