Seja uma lista dinâmica e encadeada com elementos repetidos, implemente uma rotina para eliminar todos as ocorrências de X da lista.

Passo 1

Vamos trabalhar com listas simplesmente encadeadas, em que cada nó tem um campo de valor (info) e um ponteiro para o próximo nó (next). A rotina deve receber o ponteiro para o início (head) e um valor X, e remover todos os nós cuja info seja igual a X, ajustando os ponteiros e liberando memória.

Passo 2

Primeiro precisamos tratar o caso em que o(s) nó(s) inicial(is) da lista contêm o valor X. Enquanto o nó apontado por head existir e tiver info == X, avançamos head para o próximo nó e liberamos o nó antigo.
Com o head já garantindo que ou é NULL ou info ≠ X, percorremos a lista usando dois ponteiros: prev (aponta para o nó anterior ao atual) e curr (nó que estamos testando). Inicializamos prev = head e curr = head->next.

Passo 3

Em cada iteração, se curr->info == X, ajustamos prev->next = curr->next, liberamos curr e atualizamos curr = prev->next. Caso contrário, avançamos prev = curr e curr = curr->next. Repetimos até curr ser NULL.

Passo 4

Ao final, todo nó cujo valor era X terá sido removido e a lista estará corretamente encadeada e sem vazamentos de memória.

Resposta

void removeAllX(Node** headRef, int X) {
// Remover ocorrências de X no início da lista
while (*headRef != NULL && (headRef)->info == X) {
Node
tmp = *headRef;
*headRef = (*headRef)->next;
free(tmp);
}
// Se a lista agora está vazia, encerramos
if (*headRef == NULL) return;

// Percorrer e remover ocorrências no restante
Node* prev = *headRef;
Node* curr = prev->next;
while (curr != NULL) {
    if (curr->info == X) {
        prev->next = curr->next;
        free(curr);
        curr = prev->next;
    } else {
        prev = curr;
        curr = curr->next;
    }
}
}

Exercícios relacionados