Edição didática em português. O código e suas saídas preservam o original.

Exercícios de ponteiros: inverter uma lista

Inverta ligações de uma lista simples em O(N) e libere seus nós ao terminar.

Construa uma lista encadeada de N inteiros usando malloc. Implemente reverse_list para inverter as ligações no próprio lugar, usando prev, curr e next. Retorne a nova cabeça, imprima os valores em ordem inversa e libere todos os nós.

Não copie os dados para um array auxiliar. A inversão deve percorrer cada nó uma vez e usar uma quantidade constante de ponteiros adicionais. Verifique as alocações antes de escrever.

Entrada

Primeira linha: N. Segunda linha: N inteiros separados por espaços.

Saída

Uma linha com os valores da lista invertida, separados por espaços.

Restrições

1 <= N <= 100
-10000 <= valor <= 10000
Inversão com tempo O(N) e espaço auxiliar O(1).
Aloque os nós com malloc e libere toda a memória.

Dicas

Salve curr->next antes de sobrescrever essa ligação.
Ao terminar, curr é NULL e prev aponta para a nova cabeça.

Código C

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

struct Node {
    int data;
    struct Node *next;
};

// Reverses singly linked list in-place
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement 3-pointer iterative reversal
    return NULL;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        new_node->data = val;
        new_node->next = NULL;

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    head = reverse_list(head);

    // Print list
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%c", curr->data, curr->next == NULL ? '\n' : ' ');
        curr = curr->next;
    }

    // Free memory
    curr = head;
    while (curr != NULL) {
        struct Node *temp = curr->next;
        free(curr);
        curr = temp;
    }

    return 0;
}

Abrir no compilador

Solução e explicação

Comece com prev = NULL e curr = head. Em cada repetição salve next = curr->next, altere curr->next = prev e avance com prev = curr e curr = next.

Em uma lista 1 → 2 → 3, primeiro fica 1 → NULL, depois 2 → 1 e finalmente 3 → 2 → 1. Nunca perca o ponteiro para o trecho pendente.

Para liberar, salve novamente o próximo nó antes de free. Acessar node->next depois de liberar node é uso de memória liberada. A inversão usa espaço adicional O(1); os nós originais continuam ocupando O(N).

Código da solução

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

struct Node {
    int data;
    struct Node *next;
};

struct Node* reverse_list(struct Node *head) {
    struct Node *prev = NULL;
    struct Node *curr = head;
    struct Node *next = NULL;

    while (curr != NULL) {
        next = curr->next; // Store next node pointer
        curr->next = prev; // Reverse current node's pointer backwards
        prev = curr;       // Advance prev pointer to current
        curr = next;       // Advance current pointer to next
    }

    return prev; // New head of the reversed list
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        int val;
        if (scanf("%d", &val) != 1) return 1;
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        if (new_node == NULL) return 1;
        new_node->data = val;
        new_node->next = NULL;

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    head = reverse_list(head);

    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%c", curr->data, curr->next == NULL ? '\n' : ' ');
        curr = curr->next;
    }

    // Clean up heap allocations
    curr = head;
    while (curr != NULL) {
        struct Node *temp = curr->next;
        free(curr);
        curr = temp;
    }

    return 0;
}

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.