203. Remover Elementos de uma Lista Ligada

Dado o nó cabeça head de uma lista ligada e um inteiro val, remova todos os nós com valor igual a val e retorne o novo nó cabeça. O uso de um nó sentienla simplifica a operação, evitando tratamento especial para remoção do nó cabeça.

class Solucao {
public:
    ListNode* removerElementos(ListNode* cabeca, int valorAlvo) {
        ListNode* sentinela = new ListNode(0, cabeca);
        ListNode* ponteiroAtual = sentinela;
        while (ponteiroAtual->prox != nullptr) {
            if (ponteiroAtual->prox->valor == valorAlvo) {
                ponteiroAtual->prox = ponteiroAtual->prox->prox;
            } else {
                ponteiroAtual = ponteiroAtual->prox;
            }
        }
        return sentinela->prox;
    }
};

707. Projetra uma Lista Ligada

Implemente uma lista ligada usando nós com atributos valor e prox. A classe deve fornecer métodos para obter valores, inserir no início, fim ou índice específico, e deletar por índice. A estrutura abaixo utiliza um nó sentinela para simplificar as operações.

class MinhaListaLigada {
private:
    struct No {
        int valor;
        No* prox;
        No(int v) : valor(v), prox(nullptr) {}
    };
    int tamanho;
    No* cabecaSentinela;
public:
    MinhaListaLigada() : tamanho(0), cabecaSentinela(new No(0)) {}
    int obter(int indice) {
        if (indice < 0 || indice >= tamanho) return -1;
        No* iterador = cabecaSentinela;
        for (int i = 0; i < indice; ++i) iterador = iterador->prox;
        return iterador->prox->valor;
    }
    void adicionarNoInicio(int valor) {
        No* novoNo = new No(valor);
        novoNo->prox = cabecaSentinela->prox;
        cabecaSentinela->prox = novoNo;
        ++tamanho;
    }
    void adicionarNoFim(int valor) {
        No* novoNo = new No(valor);
        No* iterador = cabecaSentinela;
        while (iterador->prox != nullptr) iterador = iterador->prox;
        iterador->prox = novoNo;
        ++tamanho;
    }
    void adicionarNoIndice(int indice, int valor) {
        if (indice < 0) indice = 0;
        if (indice > tamanho) return;
        No* novoNo = new No(valor);
        No* iterador = cabecaSentinela;
        for (int i = 0; i < indice; ++i) iterador = iterador->prox;
        novoNo->prox = iterador->prox;
        iterador->prox = novoNo;
        ++tamanho;
    }
    void deletarNoIndice(int indice) {
        if (indice < 0 || indice >= tamanho) return;
        No* iterador = cabecaSentinela;
        for (int i = 0; i < indice; ++i) iterador = iterador->prox;
        No* noParaRemover = iterador->prox;
        iterador->prox = noParaRemover->prox;
        delete noParaRemover;
        --tamanho;
    }
};

206. Inverter uma Lista Ligada

Dado o nó cabeça head de uma lista ligada, inverta a lista e retorne o novo nó cabeça. A abordagem iterativa usa três ponteiros para reverter as referências em tempo O(n) e espaço O(1).

class Solucao {
public:
    ListNode* inverterLista(ListNode* cabeca) {
        ListNode* anterior = nullptr;
        ListNode* corrente = cabeca;
        ListNode* proximo = nullptr;
        while (corrente != nullptr) {
            proximo = corrente->prox;
            corrente->prox = anterior;
            anterior = corrente;
            corrente = proximo;
        }
        return anterior;
    }
};