Edición didáctica en español. El código y sus salidas conservan el original.

Invertir una lista enlazada en C

Invierte enlaces de una lista simple en O(N) y libera sus nodos al terminar.

Construye una lista enlazada de N enteros mediante malloc. Implementa reverse_list para invertir sus enlaces en el mismo lugar, usando prev, curr y next. Devuelve la nueva cabeza, imprime los valores en orden inverso y libera todos los nodos.

No copies los datos a un array auxiliar. La inversión debe recorrer cada nodo una vez y usar una cantidad constante de punteros adicionales. Comprueba las asignaciones antes de escribir.

Entrada

Primera línea: N. Segunda línea: N enteros separados por espacios.

Salida

Una línea con los valores de la lista invertida, separados por espacios.

Restricciones

1 <= N <= 100
-10000 <= valor <= 10000
Inversión en O(N) de tiempo y O(1) de espacio auxiliar.
Asigna los nodos con malloc y libera toda la memoria.

Pistas

Guarda curr->next antes de sobrescribir ese enlace.
Al terminar, curr es NULL y prev señala la nueva cabeza.

Código C

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

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

// Reverses singly linked list in-place and returns new head
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement iterative 3-pointer reversal (prev, curr, next)
    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);

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

    return 0;
}

Abrir en el compilador

Solución y explicación

Empieza con prev = NULL y curr = head. En cada vuelta guarda next = curr->next, cambia curr->next = prev y avanza con prev = curr y curr = next.

En una lista 1 → 2 → 3, primero queda 1 → NULL, después 2 → 1 y finalmente 3 → 2 → 1. Nunca pierdas el puntero al tramo pendiente.

Para liberar, vuelve a guardar el siguiente nodo antes de free. Acceder a node->next después de liberar node es un uso de memoria liberada. La inversión usa O(1) de espacio adicional; los nodos originales siguen ocupando O(N).

Código de la solución

#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) {
        // 1. Store next node before breaking link
        next = curr->next;
        // 2. Reverse current node pointer
        curr->next = prev;
        // 3. Move prev and curr forward one step
        prev = curr;
        curr = next;
    }

    return prev; // prev is the 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;
        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);

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

    return 0;
}

Preguntas frecuentes

¿Por qué el código y la salida siguen en inglés?

Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.