1. Métodos Gerais e Classificação de Problemas

---

0. Como Percorrer uma Lista Encadeada

O código abaixo é um modelo básico de iteração, considerando que o ponteiro head pode ser nulo:

Node* atual = cabeca;
while (atual != NULL)
    atual = atual->proximo;

Para calcular o comprimento da lista, por exemplo:

Node* atual = cabeca;
int contador = 0;
while (atual != NULL) {
    contador++;
    atual = atual->proximo;
}

Para alcançar o último nó, ajustamos a condição e tratamos o caso de lista vazia:

if (!cabeca) return cabeca;
Node* atual = cabeca;
while (atual->proximo != NULL) {
    atual = atual->proximo;
}

Uma variação útil é manter um ponteiro anterior durante a travessia:

Node* anterior = NULL;
Node* atual = cabeca;
while (atual != NULL) {
    anterior = atual;
    atual = atual->proximo;
}

1. Adicionar um Nó Sentinela Antes do Início

Operações no primeiro nó geralmente exigem tratamento especial. Usar um nó fictício simplifica a lógica, como no LeetCode 203 (Remover Elementos da Lista).

2. Fusão de Duas Listas

Para percorrer duas listas simultaneamente, usamos l1 e l2. O tipo de laço (&& ou ||) define como lidar com os restos. Combinar com nó sentinela pode ser vantajoso.

while (l1 != NULL && l2 != NULL) {
    if (l1 != NULL) { /* opera em l1 */ l1 = l1->proximo; }
    if (l2 != NULL) { /* opera em l2 */ l2 = l2->proximo; }
}
// tratar o restante

Exemplo: LeetCode 2 (Adicionar Dois Números):

No* somarDoisNumeros(No* l1, No* l2) {
    No* resultado = new No(0);
    No* atual = resultado;
    int transporte = 0;
    while (l1 != NULL || l2 != NULL || transporte != 0) {
        int v1 = 0, v2 = 0;
        if (l1 != NULL) { v1 = l1->valor; l1 = l1->proximo; }
        if (l2 != NULL) { v2 = l2->valor; l2 = l2->proximo; }
        int soma = v1 + v2 + transporte;
        atual->proximo = new No(soma % 10);
        transporte = soma / 10;
        atual = atual->proximo;
    }
    return resultado->proximo;
}

Problemas relacionados: LeetCode 21 (Mesclar Listas Ordenadas), LeetCode 86 (Particionar Lista), LeetCode 328 (Lista Ímpar-Par).

3. Ponteiros Rápido e Lento (Dois Ponteiros)

Um ponteiro (lento) avança uma posição, o outro (rapido) avança duas. Isso é usado para encontrar o meio da lista ou detectar ciclos.

Iniciando ambos no head, ao final do laço, lento aponta para o meio (para número ímpar de nós) ou para o nó após o meio (para número par).

Node* lento = cabeca;
Node* rapido = cabeca;
while (rapido != NULL && rapido->proximo != NULL) {
    lento = lento->proximo;
    rapido = rapido->proximo->proximo;
}

Iniciando lento no head e rapido no segundo nó, lento aponta para o meio exato (para par, o primeiro dos dois centrais).

Node* lento = cabeca;
Node* rapido = cabeca->proximo;
while (rapido != NULL && rapido->proximo != NULL) {
    lento = lento->proximo;
    rapido = rapido->proximo->proximo;
}

Para remover o n-ésimo nó a partir do fim, faça rapido avançar n posições primeiro, depois mova ambos até rapido ser nulo.

Exemplos de uso: LeetCode 19 (Remover N-ésimo do Final), LeetCode 141 (Detectar Ciclo), LeetCode 142 (Início do Ciclo), LeetCode 160 (Interseção de Listas), LeetCode 109 (Lista para BST).

4. Processamento Interno com Ponteiros Múltiplos

Combina os padrões anteriores para modificar a estrutura da lista durante uma única passagem. Pensar no estado em um ponto médio (nó n e n+1) e nos limites (início e fim).

Exemplo clássico: reversão da lista:

Node* reverter(Node* cabeca) {
    if (cabeca == NULL || cabeca->proximo == NULL) return cabeca;
    Node* anterior = NULL;
    Node* atual = cabeca;
    while (atual != NULL) {
        Node* proximo = atual->proximo;
        atual->proximo = anterior;
        anterior = atual;
        atual = proximo;
    }
    return anterior;
}

Outros exemplos: LeetCode 24 (Troca de Pares), LeetCode 61 (Rotação), LeetCode 83/82 (Remover Duplicatas), LeetCode 206 (Reversão), LeetCode 143 (Reordenar), LeetCode 234 (Palíndromo), LeetCode 445 (Soma Reversa).

5. Ordenação de Listas

Inserção e merge sort são comuns: LeetCode 147 e LeetCode 148.

6. Outros Problemas

LeetCode 237 (Deletar Nó), LeetCode 430 (Achatar Lista Multinível).

2. Soluções e Casos de Borda

---

LeetCode 2 – Cuidado: não esquecer o transporte; usar nó sentinela para simplificar a construção da lista resultado.

LeetCode 19 – O nó sentinela resolve a exclusão do primeiro elemento.

LeetCode 21 – Laço com && exige tratar o restante após o fim; com ||, tratar nulo dentro do corpo.

LeetCode 24 – Requer antes (anterior ao par) e ponteiros para os dois nós a serem trocados. Atualizar antes corretamente.

LeetCode 61 – Solução 1: ajustar k módulo comprimento, usar ponteiro rápido; solução 2: tornar a lista circular e reposicionar.

No* rotacionarDireita(No* cabeca, int k) {
    if (!cabeca) return cabeca;
    No* p = cabeca;
    int comp = 1;
    while (p->proximo != NULL) {
        p = p->proximo;
        comp++;
    }
    p->proximo = cabeca;
    int passos = comp - (k % comp);
    for (int i = 0; i < passos; i++) p = p->proximo;
    No* novoInicio = p->proximo;
    p->proximo = NULL;
    return novoInicio;
}

LeetCode 82 – Usar antes para manter a parte já processada; pular todos os nós duplicados.

No* removerDuplicatas(No* cabeca) {
    No sentinela(0);
    sentinela.proximo = cabeca;
    No* antes = &sentinela;
    No* atual = cabeca;
    while (atual != NULL) {
        int val = atual->valor;
        bool duplicado = false;
        while (atual->proximo != NULL && atual->proximo->valor == val) {
            duplicado = true;
            atual = atual->proximo;
        }
        if (duplicado) {
            antes->proximo = atual->proximo;
        } else {
            antes = atual;
        }
        atual = atual->proximo;
    }
    return sentinela.proximo;
}

LeetCode 86 – Manter duas listas separadas (menor e maior); ao final, concatenar e definir o último nó da lista maior como NULL.

LeetCode 92 – Reverter parte da lista: localizar nó m-1, reverter de m a n, reconectar.

LeetCode 109 – Encontrar o meio (usando lento/rapido), desconectar metade esquerda, recursão.

TreeNode* listaParaBST(No* cabeca) {
    if (cabeca == NULL) return NULL;
    if (cabeca->proximo == NULL) return new TreeNode(cabeca->valor);
    No* anterior = NULL;
    No* lento = cabeca;
    No* rapido = cabeca->proximo;
    while (rapido && rapido->proximo) {
        anterior = lento;
        lento = lento->proximo;
        rapido = rapido->proximo->proximo;
    }
    TreeNode* raiz = new TreeNode(lento->valor);
    if (anterior == NULL) {
        raiz->left = NULL;
    } else {
        anterior->proximo = NULL;
        raiz->left = listaParaBST(cabeca);
    }
    raiz->right = listaParaBST(lento->proximo);
    return raiz;
}

LeetCode 138 – Usar mapa para associar cada nó original à sua cópia; resolver recursivamente.

LeetCode 141/142 – Detectar ciclo com lento/rapido. Se encontrarem, para localizar início do ciclo, reiniciar um ponteiro no início e avançar ambos no mesmo passo.

LeetCode 143 – Três passos: encontrar meio, inverter segunda metade, intercalar.

LeetCode 147 – Inserção: remover nó atual, buscar posição correta na lista ordenada (iniciando da sentinela), reinserir.

LeetCode 148 – Merge sort: encontrar meio, recursão, mesclar.

LeetCode 160 – Calcular comprimentos, alinhar caudas, avançar juntos até interseção.

LeetCode 203 – Usar sentinela e ponteiro anterior.

LeetCode 234 – Encontrar meio, inverter segunda metade, comparar.

LeetCode 237 – Copiar valor do próximo nó e pular o nó seguinte.

LeetCode 328 – Manter duas listas (posições ímpares e pares) e concatenar.

LeetCode 445 – Reverter ambas as listas, somar, reverter o resultado.

LeetCode 430 – Recursão: achatar filho e próximo; se ambos existirem, conectar e mover ao final da sublista achatada.

3. Problemas para Revisão

---

• LeetCode 61
• LeetCode 109
• LeetCode 141
• LeetCode 143
• LeetCode 147
• LeetCode 148
• LeetCode 287