Síntese: qual padrão usar?
Cinco padrões de lista ligada cobertos. Hora de treinar o reflexo: ler um enunciado e saber qual ferramenta (ou combinação) sacar — com justificativa.
A árvore de decisão da seção
1. A operação pode mexer na CABEÇA (remover/inserir no início, merge)?
→ use um DUMMY NODE para evitar casos especiais
2. Preciso de algo "a N nós do fim" ou do MEIO da lista?
├── "n-ésimo a partir do fim" → DOIS PONTEIROS com gap fixo de n
└── "meio da lista" → LENTO/RÁPIDO (fast +2, slow +1)
3. A pergunta é sobre CICLO (a lista se fecha)?
→ FLOYD (lento/rápido): se a lebre alcança a tartaruga, há ciclo
4. Preciso INVERTER a ordem (toda a lista ou um trecho)?
→ REVERSÃO IN-PLACE (três ponteiros: prev, curr, próximo)
5. Juntar duas listas ORDENADAS?
→ MERGE com dummy (costura a menor cabeça de cada vez)
6. Parece difícil / faz várias coisas?
→ DECOMPOR em peças acima (meio + reversão + merge...)
E os reflexos que valem para a seção inteira: guarde curr.next antes de
sobrescrevê-lo (ou perde o resto), e use um dummy sempre que a cabeça
puder mudar.
O mapa completo da seção
| Padrão | Pergunta-chave | Tempo | Espaço |
|---|---|---|---|
| Dummy node | "a operação mexe na cabeça?" | O(n) | O(1) |
| Dois ponteiros (gap) | "n-ésimo a partir do fim" | O(n) | O(1) |
| Lento/rápido | "meio da lista" | O(n) | O(1) |
| Floyd | "tem ciclo?" | O(n) | O(1) |
| Reversão in-place | "inverter a ordem" | O(n) | O(1) |
| Merge | "juntar duas ordenadas" | O(n+m) | O(1) |
Repare na coluna de espaço: tudo O(1). É a assinatura da seção — listas ligadas premiam quem manipula ponteiros em vez de copiar para arrays. Quando uma solução sua usar O(n) de memória, pergunte se dá para fazer só religando.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão (ou a combinação) e o porquê. 7+ acertos: pronto para a prova.
🧠 Quiz da seção: Lista Ligada
0/81. 'Verifique se uma lista ligada é um palíndromo, usando O(1) de espaço.' Qual combinação?
2. 'Encontre o nó onde duas listas se cruzam (intersecção).' Que ferramenta da seção ajuda?
3. 'Remova todos os nós com um valor específico, inclusive se for a cabeça.' Por que usar dummy?
4. 'Detecte se há ciclo e, se houver, retorne o nó onde ele começa.' Qual padrão é a base?
5. 'Some dois números representados por listas ligadas (um dígito por nó).' Qual ferramenta evita tratar a cabeça à parte?
6. 'Ordene uma lista ligada em O(n log n) e O(1) de espaço extra.' Que padrões compõem o merge sort em lista?
7. Qual a ideia-mãe que une TODA a seção de lista ligada?
8. Qual erro de implementação é o mais comum em reversão/reordenação de listas?
Pronto para a prova?
A prova final da seção Lista Ligada tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (reverter em grupos de k) combina a reversão in-place com contagem de grupos: exatamente o tipo de decomposição da aula anterior. As cinco aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".