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.
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);
}
// 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;
}
}
}