Introdução
Este artigo faz parte da nossa Série Preparação para Entrevistas. Aqui vamos resolver o problema Remove Nth Node From End of List (LeetCode 19) usando a técnica de dois ponteiros (Two Pointers) em Java, muito comum em entrevistas técnicas.
A boa notícia é que esse problema pode ser resolvido de forma elegante com Two Pointers. A ideia é simples: avançamos um ponteiro “rápido” alguns passos à frente e, em seguida, movemos rápido e lento juntos até o fim. Assim, o ponteiro lento para exatamente no nó anterior ao que precisamos remover.
Esse padrão resolve o problema em uma única passada O(n). Além disso, não é necessário calcular manualmente o tamanho da lista. Por outro lado, lida muito bem com situações delicadas, como remover o primeiro nó (quando n é igual ao tamanho da lista).
Neste artigo você vai:
Entender o enunciado com exemplos simples e visuais.
Aprender o padrão Two Pointers aplicado ao problema.
Implementar a solução em Java, com código limpo e comentários objetivos.
Revisar a complexidade de tempo e espaço e discutir erros comuns.
Entendendo o Problema: Remove Nth Node From End of List
O enunciado do “Remove Nth Node From End of List” (LeetCode 19) é simples:
Dada uma lista encadeada, remova o n-ésimo nó a partir do fim e retorne a lista ajustada.
Isso significa que, em vez de contar a partir do começo da lista, precisamos contar de trás para frente. Parece fácil, mas surgem desafios:
Como encontrar o n-ésimo nó do fim sem percorrer a lista duas vezes?
O que acontece se o nó a ser removido for o primeiro?
E se a lista tiver apenas um único elemento?
Esses são os detalhes que tornam o problema interessante em entrevistas.
Exemplo Básico
Entrada:
Lista: 1 -> 2 -> 3 -> 4 -> 5
n = 2
Saída: 1 -> 2 -> 3 -> 5
Explicação: o 2º nó a partir do fim é o 4. Ao removê-lo, a lista fica ajustada.
Remover o primeiro nó
Lista: 1 -> 2 -> 3
n = 3
Saída: 2 -> 3
Remover o último nó
Lista: 1 -> 2 -> 3
n = 1
Saída: 1 -> 2
Lista com um único elemento
Lista: 1
n = 1
Saída: [] - (lista vazia)
Remove Nth Node From End of List: solução com Two Pointers
A ideia é simples: usar dois ponteiros que percorrem a estrutura de dados em velocidades ou posições diferentes para encontrar relações específicas entre elementos.
Esse padrão é útil em vários cenários:
Detectar ciclos em uma lista encadeada.
Encontrar pares em arrays ordenados que somam um valor.
Identificar o ponto médio de uma lista.
Resolver o problema do Remove Nth Node From End of List, que estamos analisando aqui.
No nosso caso, a aplicação é direta: mantemos dois ponteiros com uma diferença de N passos. Assim, quando o ponteiro rápido chega ao final da lista, o ponteiro lento estará na posição exata para realizar a remoção.
Para visualizar melhor, veja a sequência abaixo, feita exatamente para este problema:
Passo 1 – Ambos os ponteiros começam no início da lista.
Passo 2 – O ponteiro da direita avança N posições à frente.
Passo 3 – Movemos os dois ponteiros juntos até que o da direita chegue ao final.
Passo 4 – O ponteiro da esquerda estará exatamente antes do nó que precisa ser removido, permitindo o ajuste do encadeamento.
Implementação em Java: Remove Nth Node From End of List
Agora que entendemos a técnica, vamos colocá-la em prática.
A seguir está uma implementação em Java, aplicando o padrão Two Pointers.
// Definição básica de um nó da lista encadeada
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class RemoveNthNode {
public ListNode removeNthFromEnd(ListNode head, int n) {
// Ponteiros começam na cabeça da lista
ListNode right = head;
ListNode left = head;
// Avança o ponteiro da direita n passos
for (int i = 0; i < n; i++) {
right = right.next;
}
// Caso especial: remover o primeiro nó
if (right == null) {
return head.next;
}
// Avança os dois ponteiros até o fim
while (right.next != null) {
left = left.next;
right = right.next;
}
// Remove o nó alvo
left.next = left.next.next;
return head;
}
}
Observações importantes
Caso especial: quando o nó a ser removido é o primeiro da lista, tratamos isso logo após o avanço inicial (
if (right == null)).Eficiência: a lista é percorrida apenas uma vez, resultando em tempo
O(n).
Complexidade e erros comuns no Remove Nth Node From End of List
Complexidade da solução
A solução com Two Pointers é bastante eficiente:
Tempo:
O(n), pois percorremos a lista apenas uma vez.Espaço:
O(1), já que usamos apenas variáveis auxiliares (dois ponteiros).
Isso é ideal para entrevistas, porque demonstra uma solução ótima em tempo e espaço.
Erros comuns em entrevistas
Apesar da lógica parecer simples, existem alguns pontos que geram erros frequentes:
- Esquecer o caso do primeiro nó
Se o nó a ser removido for o primeiro da lista, muitos candidatos não tratam esse caso e acabam com
NullPointerException.Nesta solução, isso foi resolvido com o
if (right == null)logo após o avanço inicial.
Avançar os ponteiros na ordem errada
Se não deslocarmos corretamente o ponteiro da direita, o da esquerda não ficará na posição certa.
A chave é garantir que a diferença entre eles seja exatamente n.
Não atualizar a referência corretamente
O ajuste
left.next = left.next.nexté essencial.Esquecer esse passo, ou manipular o nó errado, resulta em perda da lista ou em comportamento incorreto.
Tentar calcular o tamanho antes
Alguns candidatos percorrem a lista inteira, contam os nós e depois voltam para remover o alvo.
Apesar de funcionar, essa abordagem exige duas passadas e não aproveita o padrão Two Pointers.
Conclusão
O problema Remove Nth Node From End of List é um dos clássicos de entrevistas de programação.
Ele exige atenção a detalhes e também mostra se o candidato conhece padrões eficientes como o Two Pointers.
Neste artigo, vimos:
O enunciado do problema e seus casos especiais, como remover o primeiro elemento da lista.
Como aplicar a técnica Two Pointers para resolver o desafio em apenas uma passada O(n).
A implementação em Java, com código limpo e comentários objetivos.
Mais do que decorar uma solução, o importante é entender o padrão. O Two Pointers aparece em vários contextos, como detecção de ciclos, encontrar o meio de uma lista ou até em problemas com arrays ordenados. Quanto mais você praticar, mais natural será reconhecer quando essa técnica pode ser aplicada.
Se você quiser explorar o código deste problema (e de outros da série), acesse o repositório no GitHub: 👉 arte-de-programar-interviews
Quer praticar esse tipo de problema do jeito que cai em entrevistas?
Estou construindo o DevPrep, uma plataforma em português focada em raciocínio e padrões de algoritmos.
👉 Acesso por beta fechado: https://devprep.dev/