Suppression d'éléments dans une liste chaînée

Problème : Étant donné la tête d'une liste chaînée et une valeur entière, supprimer tous les nœuds où la valeur du nœud est égale à la valeur donnée et retourner la nouvelle tête.

Approche : Utiliser un nœud factice (dummy node) pour simplifier la manipulation, en particulier pour la suppression du nœud de tête. Maintenir deux pointeurs : un pour le nœud courent et un pour le précédent. Cela garantit une cohérence dans toutes les opérations, y compris pour le nœud de tête.

public ListNode supprimerElements(ListNode tete, int valeur) {
    ListNode nœudFictif = new ListNode(0, tete);
    ListNode precedent = nœudFictif;
    ListNode courant = tete;
    while (courant != null) {
        if (courant.val == valeur) {
            precedent.next = courant.next;
        } else {
            precedent = courant;
        }
        courant = courant.next;
    }
    return nœudFictif.next;
}

Complexité temporelle : O(N)
Complexité spatiale : O(1)

Conception d'une liste chaînée

Problème : Implémanter une liste chaînée avec des opérations de base : récupérer un élément par index, ajouter en tête, ajouter en queue, ajouter à un index spécifique et supprimer à un index spécifique. Les indices des nœuds commencent à 0.

Approche : Définir une classe interne pour les nœuds avec des attributs de valeur et de pointeur suivant. Uitliser un nœud factice pour simpliter les insertions et suppressions en tête. Maintenir une taille pour valider les index.

class MaListeChainee {
    private static class Noeud {
        int donnee;
        Noeud suivant;
        Noeud(int donnee) { this.donnee = donnee; }
    }

    private int longueur;
    private Noeud teteFictive;

    public MaListeChainee() {
        longueur = 0;
        teteFictive = new Noeud(0);
    }

    public int obtenir(int index) {
        if (index < 0 || index >= longueur) return -1;
        Noeud actuel = teteFictive.suivant;
        for (int i = 0; i < index; i++) {
            actuel = actuel.suivant;
        }
        return actuel.donnee;
    }

    public void ajouterEnTete(int val) {
        ajouterAIndex(0, val);
    }

    public void ajouterEnQueue(int val) {
        ajouterAIndex(longueur, val);
    }

    public void ajouterAIndex(int index, int val) {
        if (index > longueur) return;
        index = Math.max(0, index);
        longueur++;
        Noeud predecesseur = teteFictive;
        for (int i = 0; i < index; i++) {
            predecesseur = predecesseur.suivant;
        }
        Noeud nouveauNoeud = new Noeud(val);
        nouveauNoeud.suivant = predecesseur.suivant;
        predecesseur.suivant = nouveauNoeud;
    }

    public void supprimerAIndex(int index) {
        if (index < 0 || index >= longueur) return;
        longueur--;
        Noeud predecesseur = teteFictive;
        for (int i = 0; i < index; i++) {
            predecesseur = predecesseur.suivant;
        }
        predecesseur.suivant = predecesseur.suivant.suivant;
    }
}

Inversion d'une liste chaînée

Problème : Étant donné la tête d'une liste chaînée, inverser la liste et retourner la nouvelle tête.

Approche : Utiliser un nœud factice et insérer chaque nœud en tête de la nouvelle liste en parcourant l'original. Cela construit la liste inversée de manière itérative.

public ListNode inverserListe(ListNode tete) {
    ListNode nœudFictif = new ListNode(0);
    ListNode courant = tete;
    while (courant != null) {
        ListNode noeudSuivant = courant.suivant;
        courant.suivant = nœudFictif.suivant;
        nœudFictif.suivant = courant;
        courant = noeudSuivant;
    }
    return nœudFictif.suivant;
}

Complexité temporelle : O(N)
Complexité spatiale : O(1)