Compréhension des structures de liste chaînée

Prenons un exemple de liste chaînée : let liste = [1, 2, 3, 4]

Dans cette structure, liste.val vaut 1, et liste.next correspond au nœud contenant [2, 3, 4] où liste.next.val vaut 2.

Construction d'une liste chaînée à partir d'un vecteur

Convertir les éléments d'un vecteur en une liste chaînée peut se faire de deux manières :

À partir d'un vecteur de pointeurs de nœuds

std::vector<listnode> noeuds;
ListNode* premier = noeuds[0];
ListNode* courant = premier;

for (int idx = 1; idx < noeuds.size(); idx++) {
    courant->suivant = noeuds[idx];
    courant = courant->suivant;
}
</listnode>

À partir d'un vecteur de valeurs

ListNode* tete = new ListNode(valeurs[0]);
ListNode* iterateur = tete;
for (int idx = 1; idx < valeurs.size(); idx++) {
    iterateur->suivant = new ListNode(valeurs[idx]);
    iterateur = iterateur->suivant;
}
return tete;

Conversion d'une liste chaînée en vecteur

std::vector<int> elements;
ListNode* noeudCourant = teteListe;
while (noeudCourant) {
    elements.push_back(noeudCourant->valeur);
    noeudCourant = noeudCourant->suivant;
}

Tri par sélection avec une liste chaînée

for (int passe = 0; passe < compteur - 1; passe++) {
    noeudPremier = tete;
    noeudSecond = noeudPremier->suivant;
    
    while (noeudSecond) {
        if (noeudPremier->valeur > noeudSecond->valeur) {
            int tempo = noeudSecond->valeur;
            noeudSecond->valeur = noeudPremier->valeur;
            noeudPremier->valeur = tempo;
        }
        noeudPremier = noeudSecond;
        if (noeudSecond->suivant) 
            noeudSecond = noeudSecond->suivant;
        else 
            break;
    }
}

Suppression des doublons consécutifs

while (courant->suivant) {
    if (courant->valeur == courant->suivant->valeur) {
        courant->suivant = courant->suivant->suivant;
    } else {
        courant = courant->suivant;
    }
}

Utilisation d'un nœud factice (sentinelle)

ListNode* sentinelle = new ListNode(0, teteListe);
// ... traitement ...
return sentinelle->suivant;

Vérificatino d'un palindrome

On peut stocker les valeurs dans un vecteur, créer une copie inversée, puis comparer les deux vecteurs.

Détection d'intersection de deux listes

En utilisant deux pointeurs parcourant alternativement les deux listes, ils finiront par se rencontrer au point d'intersection si elle existe.

Fusion de deux listes triées

// Fonction de découpe au milieu avec pointeurs rapide et lent
ListNode* decouperListe(ListNode* depart) {
    ListNode* lent = depart;
    ListNode* rapide = depart->suivant;
    
    while (rapide && rapide->suivant) {
        lent = lent->suivant;
        rapide = rapide->suivant->suivant;
    }
    
    ListNode* milieu = lent->suivant;
    lent->suivant = nullptr;
    return milieu;
}

// Fusion de deux listes triées
ListNode* fusionner(ListNode* listeA, ListNode* listeB) {
    ListNode* fauxNoeud = new ListNode();
    ListNode* pointeur = fauxNoeud;
    
    while (listeA && listeB) {
        if (listeA->valeur < listeB->valeur) {
            pointeur->suivant = listeA;
            listeA = listeA->suivant;
        } else {
            pointeur->suivant = listeB;
            listeB = listeB->suivant;
        }
        pointeur = pointeur->suivant;
    }
    
    pointeur->suivant = listeA ? listeA : listeB;
    ListNode* resultat = fauxNoeud->suivant;
    delete fauxNoeud;
    return resultat;
}

// Tri fusion récursif
ListNode* triListe(ListNode* tete) {
    if (!tete || !tete->suivant) return tete;
    
    ListNode* premierePartie = tete;
    ListNode* deuxiemePartie = decouperListe(tete);
    
    premierePartie = triListe(premierePartie);
    deuxiemePartie = triListe(deuxiemePartie);
    
    return fusionner(premierePartie, deuxiemePartie);
}

Insertion dans une liste circulaire triée

Noeud* parcours = tete;
while (parcours->suivant != tete) {
    if (parcours->valeur > parcours->suivant->valeur) {
        if (valeurInsertion <= parcours->suivant->valeur) break;
        if (valeurInsertion >= parcours->valeur) break;
    }
    if (parcours->valeur <= valeurInsertion && 
        parcours->suivant->valeur >= valeurInsertion) {
        break;
    }
    parcours = parcours->suivant;
}
parcours->suivant = new Noeud(valeurInsertion, parcours->suivant);