Le tri d'une liste chaînée est un problème classique d'algorithmique qui nécessite une gestion efficace des pointeurs. Pour atteindre une complexité temporelle de O(n log n), plusieurs approches sont possibles, notamment le tri fusion (Merge Sort), le tri rapide (Quick Sort) ou l'utilisation d'une structure de données auxiliaire comme un tas (Heap).

Approche par Tri Fusion (Merge Sort)

Le tri fusion est particulièrement adapté aux listes chaînées car il n'exige pas d'accès aléatoire aux éléments. L'algorithme repose sur la stratégie "diviser pour régner" : on sépare la liste en deux moitiés à l'aide de la technique des pointeurs rapide et lent, on trie chaque moitié récursivement, puis on fusionne les résultats.

public class Solution {
    public ListNode trierListe(ListNode debut) {
        if (debut == null || debut.next == null) {
            return debut;
        }

        // Séparation de la liste en deux parties
        ListNode precedent = null;
        ListNode lent = debut;
        ListNode rapide = debut;

        while (rapide != null && rapide.next != null) {
            precedent = lent;
            lent = lent.next;
            rapide = rapide.next.next;
        }

        precedent.next = null; // Coupe la liste en deux

        // Tri récursif de chaque segment
        ListNode gauche = trierListe(debut);
        ListNode droite = trierListe(lent);

        return fusionner(gauche, droite);
    }

    private ListNode fusionner(ListNode l1, ListNode l2) {
        ListNode sentinelle = new ListNode(0);
        ListNode courant = sentinelle;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                courant.next = l1;
                l1 = l1.next;
            } else {
                courant.next = l2;
                l2 = l2.next;
            }
            courant = courant.next;
        }

        if (l1 != null) courant.next = l1;
        if (l2 != null) courant.next = l2;

        return sentinelle.next;
    }
}

Approche par Tri Rapide (Quick Sort)

Bien que le tri rapide soit souvent implémenté sur des tableaux, il peut être adapté aux listes chaînées. Une méthode simple consiste à échanger les valeurs des nœuds plutôt que de modifier les liaisons des pointeurs. On utilise un pivot pour partitionner la liste en deux zones : les valeurs inférieures au pivot et les valeurs supérieures.

public class QuickSortLies {
    public ListNode trier(ListNode head) {
        ordonner(head, null);
        return head;
    }

    private void ordonner(ListNode debut, ListNode fin) {
        if (debut != fin && debut.next != fin) {
            ListNode pivotNode = partitionner(debut, fin);
            ordonner(debut, pivotNode);
            ordonner(pivotNode.next, fin);
        }
    }

    private ListNode partitionner(ListNode debut, ListNode fin) {
        int valeurPivot = debut.val;
        ListNode curseurLent = debut;
        ListNode curseurRapide = debut.next;

        while (curseurRapide != fin) {
            if (curseurRapide.val < valeurPivot) {
                curseurLent = curseurLent.next;
                // Échange des données
                int temp = curseurLent.val;
                curseurLent.val = curseurRapide.val;
                curseurRapide.val = temp;
            }
            curseurRapide = curseurRapide.next;
        }

        // Placement final du pivot
        debut.val = curseurLent.val;
        curseurLent.val = valeurPivot;

        return curseurLent;
    }
}

Approche par File de Priorité (Heap Sort)

Si l'espace mémoire supplémentaire (O(n)) est autorisé, l'utilisation d'un Min-Heap (File de priorité) permet une implémentation concise. On insère tous les nœuds dans le tas, puis on les extrait un par un pour reconstruire la liste dans l'ordre croissant.

import java.util.PriorityQueue;

public class SolutionHeap {
    public ListNode trierAvecTas(ListNode head) {
        if (head == null) return null;

        PriorityQueue<ListNode> filePriorite = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        
        ListNode iterateur = head;
        while (iterateur != null) {
            ListNode suivant = iterateur.next;
            iterateur.next = null; // Détachement du nœud
            filePriorite.offer(iterateur);
            iterateur = suivant;
        }

        ListNode nouvelleTete = filePriorite.poll();
        ListNode actuel = nouvelleTete;

        while (!filePriorite.isEmpty()) {
            actuel.next = filePriorite.poll();
            actuel = actuel.next;
        }

        return nouvelleTete;
    }
}