Edizione didattica italiana

Invertire una lista concatenata semplice in C

Riorienta i collegamenti con tre puntatori e restituisci la nuova testa.

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

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

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.