0Pricing
Coding Interview Prep · Leçon

Inverser une liste chaînée

Inversez itérativement une liste simplement chaînée en réaffectant trois pointeurs, puis récursivement, en suivant chaque étape sur un schéma de type tableau blanc.

Inverser une liste chaînée est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Pourquoi l’inversion des listes est essentielle

Inverser une liste chaînée fait partie des questions d’entretien de programmation les plus fréquentes. Cela évalue votre capacité à manipuler précisément les pointeurs sans perdre la trace des nœuds. Des variantes apparaissent comme problèmes autonomes ou comme étapes intermédiaires d’algorithmes plus importants, tels que la détection des palindromes, la réorganisation d’une liste et l’inversion par groupes de k.

L’approche itérative utilise trois pointeurs : prev, curr et next_node. L’approche récursive exprime la même logique sous la forme d’un parcours de la pile d’appels. Les deux approches ont une complexité temporelle de O(n) ; l’approche itérative utilise un espace de O(1).

Inversion itérative avec trois pointeurs

À chaque étape de l’inversion itérative, enregistrez curr.next afin de ne pas perdre le reste de la liste, inversez curr.next pour le faire pointer vers l’arrière, avancez prev jusqu’à curr, puis avancez curr jusqu’au prochain nœud enregistré. Lorsque curr devient None, la boucle se termine et prev est la nouvelle tête.

Un moyen mnémotechnique utile : Enregistrer, inverser, avancer, avancer.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node  = curr.next   # Save
        curr.next  = prev        # Flip
        prev       = curr        # Advance prev
        curr       = next_node   # Advance curr
    return prev  # new head

# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
    print(head.val, end=' ')  # 5 4 3 2 1
    head = head.next

Trace pas à pas

Suivons reverse_list sur 1 -> 2 -> 3. Au départ, prev=None, curr=1. Étape 1 : enregistrez next=2, inversez 1.next=None, prev=1, curr=2. Étape 2 : enregistrez next=3, inversez 2.next=1, prev=2, curr=3. Étape 3 : enregistrez next=None, inversez 3.next=2, prev=3, curr=None. La boucle se termine ; renvoyez prev=3, qui est la nouvelle tête de 3 -> 2 -> 1.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_traced(head):
    prev, curr = None, head
    step = 0
    while curr:
        step += 1
        next_node = curr.next
        curr.next = prev
        print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
        prev = curr
        curr = next_node
    return prev

nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val)  # 3

Inversion récursive

L'approche récursive part du principe que reverse_list(head.next) renvoie la nouvelle tête du suffixe déjà inversé. Il ne reste plus qu'à inverser le pointeur entre head et head.next : définissez head.next.next = head (faites pointer l'ancien deuxième nœud vers l'ancien premier), puis head.next = None (coupez l'ancien lien vers l'avant). La nouvelle tête remonte depuis le cas de base.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list_rec(head):
    # Base case: empty or single node
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)  # reverse suffix
    head.next.next = head   # former second node points back
    head.next = None        # sever forward link
    return new_head

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
    print(head.val, end=' ')  # 4 3 2 1
    head = head.next

Inverser une sous-liste (LeetCode 92)

LeetCode 92, « Inverser une liste chaînée II », vous demande d'inverser la sous-liste allant de la position left à la position right (avec un index commençant à 1) en un seul parcours. L'astuce consiste à localiser le nœud situé avant la sous-liste (utilisez une tête factice afin que ce nœud existe toujours), puis à effectuer l'inversion à trois pointeurs exactement (right - left) fois, et enfin à reconnecter le segment inversé au reste de la liste.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    pre = dummy
    # Advance pre to node just before position 'left'
    for _ in range(left - 1):
        pre = pre.next
    curr = pre.next
    for _ in range(right - left):
        next_node   = curr.next
        curr.next   = next_node.next
        next_node.next = pre.next
        pre.next    = next_node
    return dummy.next

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
    print(head.val, end=' ')  # 1 4 3 2 5
    head = head.next

Inverser les nœuds par groupes de k (LeetCode 25)

LeetCode 25, « Inverser les nœuds par groupes de k », inverse chaque groupe consécutif de k nœuds. Procédez ainsi : vérifiez qu'il reste k nœuds ; sinon, laissez-les tels quels. Inversez les k nœuds suivants avec la méthode itérative, puis inversez récursivement le reste de la liste et reliez-le. La complexité temporelle reste O(n), avec une profondeur d'appels récursifs de O(n/k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    # Check if k nodes are available
    curr, count = head, 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head   # fewer than k nodes left, keep as-is
    # Reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # head is now the tail of the reversed group
    head.next = reverseKGroup(curr, k)
    return prev

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
    print(head.val, end=' ')  # 2 1 4 3 5
    head = head.next

Liste chaînée palindrome

LeetCode 234, « Liste chaînée palindrome » : vérifiez si une liste chaînée est un palindrome en O(n) de temps et avec un espace O(1). Stratégie : trouvez le milieu avec des pointeurs lent et rapide, inversez la seconde moitié sur place, comparez les deux moitiés nœud par nœud, puis restaurez éventuellement la liste. Cette méthode enchaîne la recherche du milieu et l'inversion — deux compétences fondamentales.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find mid
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

def build(arr):
    d = ListNode(0)
    c = d
    for v in arr:
        c.next = ListNode(v)
        c = c.next
    return d.next

print(isPalindrome(build([1,2,2,1])))  # True
print(isPalindrome(build([1,2,3])))    # False

Comparaison itérative et récursive

L'inversion itérative utilise un espace O(1) et est généralement préférable. L'inversion récursive utilise un espace de pile O(n) en raison de la profondeur des appels, ce qui peut provoquer un dépassement de pile pour les listes très longues (la limite par défaut de Python est d'environ 1 000 niveaux de récursion).

Lors d'un entretien, implémentez d'abord la version itérative pour montrer que vous tenez compte des contraintes d'espace, puis mentionnez la version récursive comme solution de remplacement plus lisible si la longueur de la liste est limitée.

import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint

# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)

Erreurs courantes lors de l'inversion

Trois erreurs sont à l'origine de presque tous les bogues d'inversion. Premièrement, ne pas enregistrer next avant de l'écraser : curr.next = prev détruit la référence vers l'avant si next_node n'a pas été enregistré. Deuxièmement, ne pas renvoyer prev : à la fin de la boucle, curr vaut None, mais prev est la nouvelle tête. Troisièmement, utiliser un mauvais cas de base récursif : oublier not head.next empêche de traiter une liste à un seul nœud et provoque une AttributeError.

# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next   # BUG if omitted: lose rest of list
        curr.next = prev
        prev      = curr
        curr      = next_node
    return prev               # BUG if you return curr: it is None

nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
    print(h.val, end=' ')  # 3 2 1
    h = h.next

Réorganiser une liste (LeetCode 143)

LeetCode 143, « Réorganiser une liste », réorganise L0 → L1 → L2 → ... → Ln en L0 → Ln → L1 → Ln-1 → L2 → Ln-2 en O(n) de temps et avec un espace O(1). La solution combine trois étapes : trouver le milieu, inverser la seconde moitié et entrelacer les deux moitiés. Maîtriser l'inversion transforme ce problème apparemment complexe en une combinaison directe d'outils familiers.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    # Find mid
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # Interleave
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
    print(h.val, end=' ')  # 1 4 2 3
    h = h.next

Résumé : l'inversion, une brique fondamentale

L'inversion d'une liste chaînée est rarement l'objectif final : c'est une brique fondamentale. La détection de palindromes, l'inversion par groupes de k, la réorganisation d'une liste et l'inversion entre deux positions reposent toutes sur le même modèle itératif à trois pointeurs. Une fois ce modèle automatisé, vous pouvez consacrer vos ressources mentales à la structure générale du problème.

Entraînez-vous toujours à l'inversion jusqu'à pouvoir l'écrire de mémoire en moins de deux minutes ; elle apparaîtra sous une forme ou une autre dans presque tous les entretiens portant sur les listes chaînées.

Vérification rapide

Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : le modèle itératif Enregistrer-Inverser-Avancer-Avancer inverse une liste en O(n) de temps et avec un espace O(1), l'approche récursive part du principe que le suffixe est déjà inversé et ne corrige que le dernier lien, et l'inversion constitue une sous-étape essentielle de la détection de palindromes, de la réorganisation d'une liste et de l'inversion par groupes de k. Nous allons maintenant étudier la détection de cycles avec l'algorithme de Floyd.

Questions Fréquemment Posées

La leçon « Inverser une liste chaînée » est-elle gratuite ?

Oui — le texte complet de « Inverser une liste chaînée » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Inverser une liste chaînée » ?

Inversez itérativement une liste simplement chaînée en réaffectant trois pointeurs, puis récursivement, en suivant chaque étape sur un schéma de type tableau blanc. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « Inverser une liste chaînée » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Classe Node et construction de listes
  2. Inverser une liste chaînée
  3. Détection de cycles avec l’algorithme de Floyd
  4. Fusionner, scinder et trouver le n-ième élément depuis la fin
← Retour à Coding Interview Prep