Reverse Linked List

Q: Comment inverser une liste chaînée sur place ?

Parcourez la liste avec deux pointeurs, prev initialisé à rien et node initialisé à la tête. À chaque nœud, sauvegardez le nœud suivant, faites pointer son lien vers prev , puis avancez prev et node d’un pas. Lorsque node arrive à la fin, prev est la tête de la liste inversée.

Q: Quelle est la complexité en temps et en espace de l’inversion d’une liste chaînée ?

La version itérative visite chaque nœud une fois, en temps O(n) , et conserve trois pointeurs, avec un espace supplémentaire de O(1) . Copier d’abord l’ordre dans un tableau prend également un temps de O(n) , mais nécessite un espace supplémentaire de O(n) . Une version récursive utilise un espace de O(n) pour la pile d’appels.

FacileListe chaînée

+10

Vous disposez d’une liste chaînée simple stockée dans le tableau next : le nœud i pointe vers le nœud next[i], -1 marque la fin de la liste et la tête est le nœud 0. Les nœuds ne sont pas stockés dans l’ordre de la liste, suivez donc les liens.

Inversez la liste en inversant chaque lien, de sorte que l’ancien dernier nœud devienne la tête et que le nœud 0 devienne le dernier nœud, pointant vers -1. Renvoyez le tableau next mis à jour, qui a la même longueur que le tableau d’entrée.

Fonction

reverseList(next: integer-array) → integer-array

nextinteger-array: l’index du nœud vers lequel chaque nœud pointe, ou -1 pour le dernier nœud
Renvoieinteger-array: le tableau suivant de la liste inversée

Contraintes

1 ≤ next.length ≤ 5000
Chaque next[i] vaut -1 ou un indice de nœud compris entre 0 et next.length-1.
En partant du nœud 0, la liste visite chaque nœud exactement une fois, puis atteint -1. Il n’y a pas de cycle.

Exemples

Entrée: next = [1, 2, 3, -1]
Sortie: [-1, 0, 1, 2]
Explication: La liste est 0 → 1 → 2 → 3. Inversée, elle devient 3 → 2 → 1 → 0, donc le nœud 3 pointe vers 2, le nœud 2 vers 1, le nœud 1 vers 0, et le nœud 0 vers -1.

Entrée: next = [2, -1, 3, 1]
Sortie: [-1, 3, 0, 2]
Explication: La liste est 0 → 2 → 3 → 1, et inversée, elle est 1 → 3 → 2 → 0. En écrivant chaque nouveau lien à l’index de son nœud, on obtient [-1, 3, 0, 2]. Inverser le tableau lui-même donnerait [1, 3, -1, 2], ce qui n’est pas la même chose.

Entrée: next = [-1]
Sortie: [-1]
Explication: Un nœud est son propre inverse. Il reste la tête et la queue, et il pointe toujours vers -1.

+11 tests cachés à la soumission

Pour aller plus loin

Peux-tu inverser uniquement la partie de la liste comprise entre la position left et la position right, en laissant les nœuds qui la précèdent et la suivent à leur place ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Inverser une liste ne déplace aucun nœud ; cela inverse chaque lien. Le problème, c’est que le lien d’un nœud est le seul moyen d’accéder au reste de la liste : dès que vous l’écrasez, tout ce qui vient après est perdu. Vous pouvez éviter ce problème en notant d’abord l’ordre, ou parcourir la liste une fois avec trois pointeurs qui mémorisent le chemin à suivre avant d’inverser chaque lien.

Notez l’ordre, puis reliez

Intuition

Dans ce problème, un pointeur est un indice de nœud, et avancer consiste à faire node = next[node]. Parcourez la liste à partir du nœud 0 jusqu’à atteindre -1, en notant chaque nœud rencontré. Dans le deuxième exemple, cela donne l’ordre [0, 2, 3, 1].

Dans la liste inversée, chaque nœud pointe vers le nœud qui le précédait dans cet ordre : 1 pointe vers 3, 3 vers 2, et 2 vers 0. Le premier nœud de l’ordre, l’ancienne tête, n’a rien avant lui, donc il pointe vers -1. Remplissez un nouveau tableau avec ces liens et renvoyez-le.

Comme chaque lien est écrit dans un nouveau tableau, rien n’est écrasé alors que vous en avez encore besoin, ce qui rend cette version difficile à rater. Elle prend un temps de O(n) et utilise une mémoire supplémentaire de O(n) pour l’ordre et le nouveau tableau.

Algorithme

Parcourez les nœuds de 0 à -1 et ajoutez chaque nœud à order.
Créez un nouveau tableau de même longueur.
Définissez l’entrée de order[0] sur -1.
Pour chaque k ≥ 1, définissez l’entrée de order[k] sur order[k-1].
Renvoyez le nouveau tableau.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Inverser les liens en une seule passe

Intuition

Tu peux inverser chaque lien dès que tu atteins son nœud, si tu te souviens du nœud d’où tu viens. Garde prev, le nœud derrière toi, en commençant à -1, car l’ancienne tête deviendra le dernier nœud. Au niveau de node, le lien next[node] pointe vers l’avant ; définis-le sur prev pour qu’il pointe vers l’arrière.

Cette écriture détruit ton seul moyen d’avancer ; sauvegarde donc d’abord sa valeur dans une troisième variable, after = next[node]. Inverse ensuite le lien, puis déplace les deux pointeurs d’un pas : prev = node, node = after. À tout moment, les nœuds derrière toi forment une liste inversée dont prev est la tête, et les nœuds devant toi sont le reste intact, qui commence à node. Lorsque node atteint -1, tous les liens ont été inversés et prev est la nouvelle tête.

Dans le deuxième exemple, les pointeurs parcourent les nœuds 0, 2, 3, 1, en écrivant next[0] = -1, next[2] = 0, next[3] = 2 et next[1] = 3. Chaque nœud est visité une fois, en un temps O(n), et la seule mémoire utilisée est celle de trois entiers, soit O(1).

Algorithme

Définissez prev = -1 et node = 0.
Tant que node n’est pas -1, enregistrez after = next[node].
Définissez next[node] = prev.
Passez à la suite : prev = node, puis node = after.
Renvoyez next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Pièges et cas limites

Presque tous les bugs ici concernent l’ordre des trois affectations ou les deux extrémités de la liste.

Écraser next[node] avant de l’avoir sauvegardé. Après next[node] = prev, l’ancien lien vers l’avant est perdu, et le parcours repart en arrière au lieu de continuer vers le nœud suivant.
Initialiser prev avec une valeur autre que -1. L’ancienne tête doit terminer la nouvelle liste. L’initialiser à 0 fait pointer le nœud 0 vers lui-même.
Inverser le tableau au lieu des liens. Les nœuds ne sont pas stockés dans l’ordre de la liste, et la réponse conserve chaque nœud à son propre index ; seules les valeurs changent. Inverser [2, -1, 3, 1] donne [1, 3, -1, 2], et non [-1, 3, 0, 2].
S’arrêter un nœud trop tôt avec une boucle sur next[node] != -1. Il faut aussi inverser le lien du dernier nœud, donc continuer la boucle tant que node != -1.
Inverser une longue liste avec la récursion. Une liste de 5000 nœuds nécessite 5000 appels imbriqués, ce qui dépasse la limite de 1000 de Python.
Oublier le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les index des nœuds à partir de 0 et lisez next[node + 1]. Ruby et R réservent le mot next, donc les solutions de départ nomment le paramètre next_.

Questions fréquentes4

Comment inverser une liste chaînée sur place ?

Parcourez la liste avec deux pointeurs, prev initialisé à rien et node initialisé à la tête. À chaque nœud, sauvegardez le nœud suivant, faites pointer son lien vers prev, puis avancez prev et node d’un pas. Lorsque node arrive à la fin, prev est la tête de la liste inversée.

Quelle est la complexité en temps et en espace de l’inversion d’une liste chaînée ?

La version itérative visite chaque nœud une fois, en temps O(n), et conserve trois pointeurs, avec un espace supplémentaire de O(1). Copier d’abord l’ordre dans un tableau prend également un temps de O(n), mais nécessite un espace supplémentaire de O(n). Une version récursive utilise un espace de O(n) pour la pile d’appels.

Peux-tu inverser une liste chaînée de manière récursive ?

Oui. Inverse tout ce qui suit la tête, puis fais pointer vers la tête l’ancien nœud suivant de la tête et définis le lien de la tête comme étant vide. Cela se lit bien, mais effectue un appel imbriqué par nœud, donc une longue liste peut faire déborder la pile d’appels. Python s’arrête à 1000 appels par défaut, ce qu’une liste de 5000 nœuds dépasse.

Pourquoi faut-il trois pointeurs pour inverser une liste chaînée ?

Pour inverser le lien d’un nœud, tu as besoin du nœud lui-même et du nœud qui le précède, soit deux pointeurs. Le troisième contient le nœud suivant, car inverser le lien efface la seule référence au reste de la liste. Sans lui, le parcours ne peut pas continuer.

Python

def reverseList(next):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

next = [1, 2, 3, -1]

Attendu

[-1, 0, 1, 2]