Padrão 1: Dummy node e dois ponteiros
Duas ferramentas que aparecem em quase todo problema de lista: o nó sentinela (dummy), que elimina o caso especial "e se for a cabeça?", e os dois ponteiros com distância fixa, que resolvem "a partir do fim" em uma passada.
Tente primeiro: Remove Nth Node From End of 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.
Remova o n-ésimo nó a partir do fim da lista e retorne a cabeça. Tente fazer em uma única passada.
Exemplo: 1 → 2 → 3 → 4 → 5, n = 2 → remove o 4 → 1 → 2 → 3 → 5.
Tentou? A saída natural é: contar o tamanho da lista numa passada e, em outra, andar até o nó certo — duas passadas, e ainda tratar à parte o caso de remover a cabeça. A teoria abaixo faz tudo numa passada e sem caso especial.
A teoria 1: o nó dummy (sentinela)
Operações na cabeça são chatas porque a cabeça não tem "nó anterior" para
religar. Resultado: um monte de if head is None e if no_anterior is None
espalhados.
O truque do dummy: crie um nó falso que aponta para a cabeça real.
dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ ∅
Agora todo nó de verdade tem um anterior (no pior caso, o dummy). Você
opera sem casos especiais e, no final, retorna dummy.next — que é a cabeça
(possivelmente nova). Some um nó de papel, ganhe um código sem ramificações.
A teoria 2: dois ponteiros com distância fixa
Para perguntas do tipo "o n-ésimo a partir do fim", você não sabe onde é o fim sem percorrer. A sacada: mantenha dois ponteiros com um intervalo fixo de n nós entre eles.
- Avance o
fastn passos à frente. - Mova
fasteslowjuntos atéfastchegar ao fim. - Como a distância entre eles é n, quando
fastacaba,slowestá exatamente n nós antes do fim — bem onde você precisa para religar.
Uma passada, sem contar o tamanho antes. Combinado com o dummy (para o caso de remover a cabeça), o código fica limpo:
Por que é O(n) tempo e O(1) espaço?
Cada ponteiro percorre a lista uma vez (fast anda n + resto; slow anda
resto) — total O(n), uma única passada. Usamos só alguns ponteiros, nenhum
array auxiliar → O(1) de espaço. A versão "contar e depois andar" também é
O(n), mas faz duas passadas e precisa do caso especial da cabeça (que o
dummy elimina).
Quando usar cada um
- Dummy node: sempre que a operação pode mexer na cabeça (remover,
inserir no início, merge). Custa um nó e remove um monte de
if. - Dois ponteiros com gap: "n-ésimo a partir do fim", "remova o do meio", qualquer "posição relativa ao fim" em uma passada.
🧠 Quiz de fixação
0/41. Para que serve o nó dummy (sentinela)?
2. No 'n-ésimo a partir do fim', por que avançar o fast n passos antes de mover os dois juntos resolve em uma passada?
3. Por que o dummy é especialmente útil em 'remover o n-ésimo a partir do fim'?
4. Qual a complexidade do remove-nth com dois ponteiros + dummy?
Resumo
- Dummy node: um nó sentinela antes da cabeça remove os casos especiais de
operar no início; retorne
dummy.next. - Dois ponteiros com gap de n: resolve "a partir do fim" em uma passada, sem contar o tamanho.
- Juntos: O(n) tempo, O(1) espaço, sem ramificações feias.
Próxima aula: o padrão mais clássico da seção — reversão in-place.