24 de Março
Inverter lista encadeada
Como sair da reconstrucao com array e entender a ideia central de ponteiros em lista encadeada.
Lista Encadeada Iniciante 15 min TypeScript
Dada a cabeca de uma lista encadeada simples, inverta a lista e retorne a nova cabeca.
Exemplo:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
O que perceber antes de codar
- Você retorna a nova cabeca da lista invertida.
- O desafio e mudar a direção dos ponteiros sem perder o resto da lista.
- Lista vazia e lista com um no só continuam validas.
Erros comuns
- sobrescrever `current.next` antes de guardar o próximo no
- retornar `head` no final em vez da nova cabeca
Passo 1 — Entender o que muda numa lista encadeada
Em array, inverter costuma ser troca de posição.
Em lista encadeada, o valor de cada no nem precisa mudar.
O que muda e o ponteiro next.
O problema inteiro e sobre isso:
- quem aponta para quem agora
- como mudar isso sem perder o resto da lista
Passo 2 — Escrever uma versão inicial correta
Uma versão inicial simples e guardar os valores num array e reconstruir uma nova lista ao contrario:
export function reverseList(head) {
const values = []
let current = head
while (current) {
values.push(current.val)
current = current.next
}
let newHead = null
for (const value of values) {
newHead = { val: value, next: newHead }
}
return newHead
}
Funciona. Mas cria estrutura nova e foge do ponto principal do problema.
Passo 3 — Perguntar o que precisa acontecer em cada no
Quando você esta em current, quer inverter a seta:
- antes:
current -> next - depois:
current -> previous
Mas se você fizer isso sem cuidado, perde o resto da lista.
Entao a ordem certa e:
- guardar
nextNode - inverter
current.next - avancar os ponteiros
Passo 4 — Caminhar carregando tres referencias
As tres referencias sao:
previouscurrentnextNode
No fim, previous vira a nova cabeca.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function reverseList(head) {
// head is an object like { val: number, next: ... } or null
// sua solução aqui
return head
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 — Reconstruir com array O(n) de memória extra
Boa versão inicial para validar entendimento.
export function reverseList(head) {
const values = []
let current = head
while (current) {
values.push(current.val)
current = current.next
}
let newHead = null
for (const value of values) {
newHead = { val: value, next: newHead }
}
return newHead
}Correta, mas não trabalha a habilidade principal de lista encadeada.
Solução 2 — Ponteiros no próprio lugar O(1) de memória extra
Agora a ideia e inverter os ponteiros durante a passada.
export function reverseList(head) {
let previous = null
let current = head
while (current) {
const nextNode = current.next
current.next = previous
previous = current
current = nextNode
}
return previous
}O algoritmo parece curto, mas ele só funciona porque a ordem dos passos protege a parte da lista que ainda falta processar.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial pode reconstruir a lista com um array, mas a solução forte inverte os ponteiros no próprio lugar. Em cada no eu salvo o próximo, faco
current.next = previous, e depois avanço. No fim,previousvira a nova cabeca comO(1)de memória extra.
Isso mostra que você:
- entende a diferença entre array e
lista encadeada - sabe manipular ponteiros sem perder referência
- explica a ordem das operações com clareza
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- reencadear nos
- percorrer lista carregando estado anterior
- mudar direção de ponteiros
- resolver problemas de lista sem memória extra
O ponto não e decorar esse problema.
O ponto e aprender a controlar referencias sem se perder.