Problème

Étant donné une liste chaînée simplement chaînée, déterminer si elle constitue un palindrome.

Suivi : Peut-on résoudre ce problème en O(n) temps et O(1) espace ?

Analyse

L'objectif est de vérifier si une liste chaînée est symétrique (palindrome).

Solution 1 : Approche avec tableau auxiliaire

Une première idée consiste à parcourir la liste une première fois pour stocker les valeurs dans un vecteur, puis à effectuer une seconde traversal pour comparer les éléments symétriques.

// Définition du nœud de la liste chaînée
struct Noeud {
    int donnee;
    Noeud* suivant;
    Noeud(int x) : donnee(x), suivant(nullptr) {}
};

class Solution {
public:
    bool estPalindrome(Noeud* tete) {
        vector<int> valeurs;
        Noeud* courant = tete;
        
        // Stockage des valeurs
        while (courant) {
            valeurs.push_back(courant->donnee);
            courant = courant->suivant;
        }
        
        // Comparaison symétrique
        for (int debut = 0, fin = valeurs.size() - 1; debut < fin; debut++, fin--) {
            if (valeurs[debut] != valeurs[fin]) return false;
        }
        return true;
    }
};

Complexité : O(n) temps et O(n) espace.

Solution 2 : Approche avec inversion partielle

Pour réduire la complexité spatiale à O(1), on peut :

1. Trouver le milieu de la liste avec deux pionteurs (lent et rapide)
2. Invreser la seconde moitié
3. Comparer les deux moitiés simultanément

class Solution {
public:
    bool estPalindrome(Noeud* tete) {
        if (!tete || !tete->suivant) return true;
        
        Noeud* milieu = trouverMilieu(tete);
        Noeud* deuxiemePartie = inverserListe(milieu);
        
        // Comparaison des deux parties
        Noeud* premiere = tete;
        Noeud* deuxieme = deuxiemePartie;
        while (premiere && deuxieme) {
            if (premiere->donnee != deuxieme->donnee) return false;
            premiere = premiere->suivant;
            deuxieme = deuxieme->suivant;
        }
        return true;
    }
    
private:
    Noeud* trouverMilieu(Noeud* tete) {
        Noeud* lent = tete;
        Noeud* rapide = tete;
        Noeud* precedent = nullptr;
        
        while (rapide && rapide->suivant) {
            rapide = rapide->suivant->suivant;
            precedent = lent;
            lent = lent->suivant;
        }
        
        if (precedent) precedent->suivant = nullptr; // Couper la liste
        return lent;
    }
    
    Noeud* inverserListe(Noeud* tete) {
        Noeud* precedent = nullptr;
        Noeud* courant = tete;
        
        while (courant) {
            Noeud* suivantTemp = courant->suivant;
            courant->suivant = precedent;
            precedent = courant;
            courant = suivantTemp;
        }
        return precedent;
    }
};

Complexité : O(n) temps et O(1) espace.

Solution 3 : Approche récursive avec pointeurs

Une alternative récursive utilise également la technique des pointeurs rapide et lent, avec une pile d'appels ipmlicite :

class Solution {
private:
    Noeud* milieuListe;
    
    bool verifierRecursif(Noeud* lent, Noeud* rapide) {
        if (!rapide) {
            milieuListe = lent;
            return true;
        }
        if (!rapipe->suivant) {
            milieuListe = lent->suivant;
            return true;
        }
        
        bool resultat = verifierRecursif(lent->suivant, rapide->suivant->suivant);
        
        if (resultat && lent->donnee == milieuListe->donnee) {
            milieuListe = milieuListe->suivant;
            return true;
        }
        return false;
    }
    
public:
    bool estPalindrome(Noeud* tete) {
        return verifierRecursif(tete, tete);
    }
};