Probleme – Une liste chaînée, et ses trois pièges

1. Les trois opérations.

typedef struct maillon_s { int valeur; struct maillon_s* suivant; } maillon;

/* Renvoie la nouvelle tête, ou l'ancienne si l'allocation échoue. */
maillon* inserer_tete(maillon* tete, int x) {
    maillon* neuf = malloc(sizeof(maillon));
    if (neuf == NULL) { return tete; }
    neuf->valeur = x;
    neuf->suivant = tete;
    return neuf;
}

/* Nombre de maillons. Complexité : Theta(n). */
int longueur(const maillon* tete) {
    int n = 0;
    for (const maillon* m = tete; m != NULL; m = m->suivant) { n = n + 1; }
    return n;
}

/* Libère toute la chaîne. */
void detruire(maillon* tete) {
    while (tete != NULL) {
        maillon* suiv = tete->suivant;    /* RETENIR avant de libérer */
        free(tete);
        tete = suiv;
    }
}

2. Le renversement en place.

/* Renverse la liste et renvoie la nouvelle tête. Ne réalloue rien.
   Précondition : tete est une chaîne valide (éventuellement NULL). */
maillon* renverser(maillon* tete) {
    maillon* precedent = NULL;
    maillon* courant = tete;
    /* INVARIANT : precedent est la tête de la portion DÉJÀ renversée,
       courant est la tête de la portion RESTANTE, et les deux portions
       forment ensemble les maillons de la liste initiale. */
    while (courant != NULL) {
        maillon* suiv = courant->suivant;   /* on retient AVANT de casser */
        courant->suivant = precedent;       /* on retourne le lien */
        precedent = courant;
        courant = suiv;
    }
    return precedent;
}

3. La preuve.

Terminaison. Variant : le nombre de maillons restant dans la portion pointée par courant. À chaque tour, courant avance d'un maillon vers NULL : le variant décroît strictement de $1$ et reste positif. La boucle fait exactement $n$ tours.

Correction. L'invariant est celui écrit dans le code. À l'initialisation, la portion renversée est vide (precedent vaut NULL) et la portion restante est la liste entière : l'invariant tient. À chaque tour, on détache le premier maillon restant et on le pose en tête de la portion renversée — les deux portions restent complémentaires, et la renversée reste bien renversée. À la sortie, courant vaut NULL : la portion restante est vide, donc precedent est la liste entière renversée.

Les trois pièges de ce problème, et ils sont tous dans le renversement :

• retenir suiv avant d'écraser courant->suivant — sinon on perd le reste de la liste, définitivement ;
• rendre precedent et non courant — à la sortie, courant vaut NULL ;
• traiter la liste vide : avec tete == NULL, la boucle ne s'exécute pas et l'on rend NULL. C'est correct par construction, sans cas particulier — le signe d'un code bien posé.