Desafio C

Inverter lista encadeada

Enunciado

Implemente uma função inverter que inverte a ordem dos nós de uma lista encadeada simples, retornando o novo ponteiro para a cabeça. A inversão deve ser feita in-place, ou seja, sem alocar novos nós. Além disso, garanta que a memória original seja preservada (nenhum nó é liberado).

Requisitos

  • A função deve inverter a lista alterando apenas os ponteiros prox.
  • Não alocar novos nós.
  • Retornar a nova cabeça (que era o último nó).
  • A lista original deve ser modificada in-place.

Código inicial

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

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

No* inverter(No *head) {
    // 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: 1 -> 2 -> 3 -> 4 -> NULL
    // inverter
    // imprimir resultado
    return 0;
}

Saída esperada

4 -> 3 -> 2 -> 1 -> NULL
Ver dica

Use três ponteiros: ant, atual e prox. A cada iteração, inverta o ponteiro prox do nó atual para apontar para o anterior.

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

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

No* inverter(No *head) {
    No *ant = NULL;
    No *atual = head;
    No *prox = NULL;

    while (atual) {
        prox = atual->prox; // guarda o próximo
        atual->prox = ant;  // inverte o ponteiro
        ant = atual;        // avança ant
        atual = prox;       // avança atual
    }
    return ant; // nova cabeça
}

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, 1);
    lista = inserir_fim(lista, 2);
    lista = inserir_fim(lista, 3);
    lista = inserir_fim(lista, 4);

    lista = inverter(lista);
    imprimir(lista);
    liberar(lista);
    return 0;
}

Passo a passo

  1. Inicializamos ant = NULL, atual = head e prox = NULL.
  2. Enquanto atual não for NULL:
    • prox = atual->prox guarda o próximo nó antes de modificar.
    • atual->prox = ant inverte o ponteiro do nó atual para o anterior.
    • ant = atual avança o anterior.
    • atual = prox avança para o próximo nó.
  3. Ao final, ant aponta para a nova cabeça (último nó da lista original).
  4. Retornamos ant.
  5. No main, criamos a lista, invertemos e imprimimos.

Por que funciona

A inversão é feita iterativamente, revertendo o sentido dos ponteiros. Cada nó passa a apontar para o seu antecessor. O ponteiro prox evita perder o resto da lista. No final, o antigo último nó se torna a nova cabeça.

Erros comuns

  • Não guardar o próximo nó antes de inverter: se fizer atual->prox = ant sem salvar prox, perde-se o resto da lista.
  • Retornar head em vez de ant: a nova cabeça é ant.
  • Esquecer de inicializar ant = NULL: o primeiro nó deve apontar para NULL.
  • Modificar a lista e não liberar depois: a memória ainda precisa ser liberada no final.

Outra forma de resolver

Usar recursão:

No* inverter_rec(No *head) {
    if (!head || !head->prox) return head;
    No *nova = inverter_rec(head->prox);
    head->prox->prox = head;
    head->prox = NULL;
    return nova;
}

Essa abordagem é elegante, mas usa pilha de recursão, podendo estourar para listas muito longas.

Saída esperada

4 -> 3 -> 2 -> 1 -> NULL