Edizione didattica italiana

Puntatori in C: invertire una lista

Inverti i collegamenti di una lista semplice e libera correttamente i nodi.

Costruisci una lista dai valori letti. reverse_list deve invertire i collegamenti dei nodi esistenti e restituire la nuova testa senza creare una seconda lista.

Dopo la stampa libera tutti i nodi. Controlla ogni malloc: un errore non deve portare a dereferenziare NULL o perdere i nodi già allocati.

Input

N, poi N interi nell’ordine iniziale della lista.

Output

Valori della lista invertita su una riga, separati da spazi.

Vincoli

1 ≤ N ≤ 100; valori da -10000 a 10000.
Inversione in O(N) tempo e O(1) memoria aggiuntiva.

Suggerimenti

Mantieni i puntatori prev, curr e next.
Salva curr->next prima di modificare il collegamento corrente.
Alla fine prev indica la nuova testa.

Codice sorgente

#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;
}

Apri nel compilatore

Spiegazione della soluzione

Inizializza prev a NULL e curr alla testa. A ogni passo salva next, assegna curr->next = prev, poi avanza prev e curr.

Traccia 1 → 2 → 3: la nuova testa deve essere 3 e l’ultimo collegamento NULL. I nodi occupano O(N) memoria, ma l’inversione aggiunge soltanto tre puntatori.

Per liberare la lista salva il collegamento successivo prima di free. Non accedere più al nodo liberato.

Codice della soluzione

#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;
}

Domande frequenti

Perché il codice e alcuni risultati restano in inglese?

Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.