Édition pédagogique en français

Inverser une liste simplement chaînée en C

Réorientez les liens existants avec trois pointeurs et restituez la nouvelle tête de liste.

Construisez une liste à partir des entiers lus. La fonction reverse_list doit inverser les liens des nœuds existants et renvoyer la nouvelle tête, sans créer une seconde liste.

Après l’affichage, libérez tous les nœuds. Vérifiez chaque allocation : un échec de malloc ne doit pas entraîner le déréférencement d’un pointeur nul ni perdre les nœuds déjà alloués.

Entrée

N, puis N entiers dans l’ordre initial de la liste.

Sortie

Les valeurs de la liste inversée sur une ligne, séparées par des espaces.

Contraintes

1 ≤ N ≤ 100 ; valeurs entre -10000 et 10000.
Inversion en O(N) temps avec O(1) mémoire supplémentaire.

Indices

Conservez les pointeurs prev, curr et next.
Sauvegardez curr->next avant de modifier le lien du nœud courant.
À la fin, prev désigne la nouvelle tête.

Code source

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

Ouvrir dans le compilateur

Explication de la solution

Initialisez prev à NULL et curr à la tête. À chaque étape, mémorisez next, affectez curr->next = prev, puis avancez prev et curr.

Tracez une liste 1 → 2 → 3 pour vérifier que la nouvelle tête vaut 3 et que le dernier lien vaut NULL. Les nœuds initiaux occupent O(N) mémoire, mais l’inversion n’ajoute que trois pointeurs.

Pour libérer la liste, sauvegardez le lien suivant avant free. N’accédez plus au nœud une fois sa mémoire libérée.

Code de la solution

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

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.