Médio C

Remover todas as ocorrências

Enunciado

Implemente uma função remover_todas que remove todos os nós que contenham um determinado valor inteiro da lista encadeada. A função deve retornar o ponteiro para a nova cabeça da lista.

Requisitos

  • A função deve percorrer a lista e remover todos os nós com o valor alvo.
  • Ajustar corretamente os ponteiros para não quebrar a lista.
  • Liberar a memória dos nós removidos com free.

Código inicial

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *prox;
} No;

No* remover_todas(No *head, int valor) {
    // TODO: implemente
}

void imprimir(No *head) {
    for (No *p = head; p; p = p->prox)
        printf("%d -> ", p->valor);
    printf("NULL\n");
}

int main(void) {
    // criar lista: 10 -> 20 -> 10 -> 30 -> 10 -> NULL
    // chamar remover_todas(lista, 10)
    // imprimir resultado
    return 0;
}

Saída esperada

20 -> 30 -> NULL
Ver dica

Use um ponteiro para ponteiro (No **) ou dois ponteiros (ant e atual) para lidar com a remoção da cabeça e de nós consecutivos.

Mostrar solução 
#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *prox;
} No;

No* remover_todas(No *head, int valor) {
    No *ant = NULL;
    No *atual = head;

    while (atual) {
        if (atual->valor == valor) {
            No *remover = atual;
            if (ant) {
                ant->prox = atual->prox; // pula o nó
            } else {
                head = atual->prox; // remove a cabeça
            }
            atual = atual->prox;
            free(remover);
        } else {
            ant = atual;
            atual = atual->prox;
        }
    }
    return head;
}

void imprimir(No *head) {
    for (No *p = head; p; p = p->prox)
        printf("%d -> ", p->valor);
    printf("NULL\n");
}

No* inserir_fim(No *head, int valor) {
    No *novo = malloc(sizeof(No));
    novo->valor = valor;
    novo->prox = NULL;
    if (!head) return novo;
    No *p = head;
    while (p->prox) p = p->prox;
    p->prox = novo;
    return head;
}

void liberar(No *head) {
    while (head) {
        No *prox = head->prox;
        free(head);
        head = prox;
    }
}

int main(void) {
    No *lista = NULL;
    lista = inserir_fim(lista, 10);
    lista = inserir_fim(lista, 20);
    lista = inserir_fim(lista, 10);
    lista = inserir_fim(lista, 30);
    lista = inserir_fim(lista, 10);

    lista = remover_todas(lista, 10);
    imprimir(lista);
    liberar(lista);
    return 0;
}

Passo a passo

  1. Inicializamos ant = NULL e atual = head.
  2. Enquanto atual não for NULL, verificamos se atual->valor == valor.
  3. Se for igual, guardamos o nó em remover.
  4. Se ant não for NULL, fazemos ant->prox = atual->prox; senão, a cabeça passa a ser atual->prox.
  5. Avançamos atual para o próximo nó e liberamos remover.
  6. Se não for igual, atualizamos ant = atual e avançamos atual.
  7. Retornamos head (que pode ter mudado se a cabeça foi removida).
  8. No main, criamos a lista, chamamos remover_todas e imprimimos.

Por que funciona

A função percorre a lista mantendo o nó anterior. Quando encontra o valor, ajusta o ponteiro do anterior para pular o nó atual e libera a memória. Isso remove todas as ocorrências, inclusive múltiplas seguidas. A cabeça é atualizada quando necessário.

Erros comuns

  • Não atualizar ant após remover: se ant não for atualizado, o próximo nó pode ser perdido. No código, quando removemos, ant permanece o mesmo, o que está correto porque o novo atual já é o próximo.
  • Esquecer de liberar a memória: causa vazamento.
  • Não tratar remoção da cabeça: se ant for NULL, é preciso atualizar head.
  • Acessar atual->prox após free: no código, guardamos remover e avançamos atual antes de liberar, evitando usar memória liberada.

Outra forma de resolver

Usar um ponteiro para ponteiro:

No* remover_todas(No *head, int valor) {
    No **pp = &head;
    while (*pp) {
        if ((*pp)->valor == valor) {
            No *remover = *pp;
            *pp = remover->prox;
            free(remover);
        } else {
            pp = &(*pp)->prox;
        }
    }
    return head;
}

Essa versão é mais concisa e evita a variável ant.

Saída esperada

20 -> 30 -> NULL