Padrão 2: Reversão in-place
Inverter uma lista ligada é o problema mais clássico da seção — e o que mais aparece como peça de problemas maiores. O truque: caminhar pela lista virando cada ponteiro para trás, com cuidado para não perder o resto.
Tente primeiro: Reverse Linked 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.
Inverta uma lista ligada e retorne a nova cabeça. A lista é head = ListNode (cada nó tem .val e .next; o último aponta para None/null).
Exemplo: 1 → 2 → 3 → 4 → 5 vira 5 → 4 → 3 → 2 → 1.
(Para testar, passamos a lista como array e comparamos o resultado como array.)
Tentou? Uma saída é copiar os valores para um array, inverter e reconstruir — mas isso gasta O(n) de memória. A teoria abaixo inverte no lugar, com O(1) de espaço, só repointando os
next.
A teoria: virar os ponteiros, um a um
Inverter a lista significa que cada next, que apontava para frente, passa a
apontar para trás. O perigo: se você fizer curr.next = anterior sem
guardar antes para onde curr apontava, você perde o resto da lista.
Por isso o padrão usa três ponteiros:
prev: o nó anterior (começa emNone— antes da cabeça não há nada);curr: o nó atual (começa na cabeça);- um temporário (
seguinte): guardacurr.nextantes de sobrescrevê-lo.
A cada passo, a dança é sempre a mesma:
1. seguinte = curr.next (guarda para não perder o resto)
2. curr.next = prev (vira o ponteiro para trás)
3. prev = curr (avança prev)
4. curr = seguinte (avança curr)
Quando curr chega a None, prev é o último nó visitado — ou seja, a
nova cabeça. Veja os ponteiros (prox) invertendo um a um:
Por que é O(n) tempo e O(1) espaço?
O laço visita cada nó exatamente uma vez (curr anda do início ao fim),
fazendo trabalho O(1) por nó (quatro atribuições) → O(n) de tempo. Não
criamos nenhuma estrutura nova — só três ponteiros que andam — então
O(1) de espaço. Copiar para um array e reconstruir também seria O(n) de
tempo, mas com O(n) de espaço; a reversão in-place é estritamente melhor.
| Solução | Tempo | Espaço |
|---|---|---|
| Copiar valores p/ array e reconstruir | O(n) | O(n) |
| Reversão in-place (3 ponteiros) | O(n) | O(1) |
A mesma ideia, com ListNode de verdade
No editor você manipula node.next diretamente. É a mesma dança de três
ponteiros:
Por que vale tanto dominar isto
A reversão in-place é uma peça de Lego. Reverter só uma parte da lista, reverter em grupos de k (um problema "difícil"!), checar se a lista é um palíndromo, reordenar — todos usam essa mesma dança de três ponteiros como sub-rotina. Quem automatiza a reversão destrava metade dos problemas difíceis da seção. Repita a dança até ela sair sem pensar.
🧠 Quiz de fixação
0/41. Por que a reversão precisa guardar curr.next num temporário ANTES de fazer curr.next = prev?
2. Por que prev começa em None?
3. Ao fim do laço (curr == None), o que é prev?
4. Qual a vantagem da reversão in-place sobre copiar para um array?
Resumo
- Reverter = virar cada
nextpara trás, com três ponteiros (prev, curr, temporário). - Guarde
curr.nextantes de sobrescrever, ou perde o resto da lista. - O(n) tempo, O(1) espaço — melhor que copiar para um array.
- É peça de Lego de muitos problemas difíceis (reverter em grupos, palíndromo, reordenar).
Próxima aula: dois ponteiros em velocidades diferentes — o meio da lista e a detecção de ciclos.