On se retrouve en ce début d’année avec une nouvelle série d’articles consacrée aux questions techniques posées en entretien et plus particulièrement aux tests d’algorithmiques.
Les tests d’algorithmiques ne sont plus uniquement présents chez les géants du secteur puisque de plus en plus de sociétés font passer ce genre d’entretien aux candidats.
Même si la plupart du temps ces tests ne sont pas adaptés à la difficulté du poste, vous devez y être préparé.
Néanmoins en dehors des entretiens, résoudre et comprendre des problèmes d’algorithmiques fait partie des compétences essentielles d’un développeur.
Pour ce premier article, nous allons nous intéresser aux listes chaînées et voir les questions pouvant être posées en entretiens concernant celles-ci.
Note : Pour cet article, je fais abstraction des spécificités de chaque langage pour me concentrer uniquement sur la partie algorithmique. J’ai également fait le choix de commencer cette série avec les listes chaînées, car c’est l’une des structures de données linéaires les moins maîtrisées par les candidats contrairement aux tableaux. Je fais néanmoins un rappel sur les tableaux dans cet article. Un article en partie dédié (en plus des chaînes de caractères) leur sera sûrement consacré. Le langage choisi pour mes exemples de code est le JavaScript car c’est le langage utilisé par la plupart de mes lecteurs. J’ai hésité à mettre, en plus du JavaScript, les exemples en Python mais je n’ai pas voulu surcharger l’article, vous arriverez néanmoins facilement à traduire ceux-ci dans un autre langage.
Qu’est-ce qu’une liste chaînée ?
Avant de voir les différentes questions d’algorithmiques concernant les listes chaînées, il est bon de rappeler ce qu’est une liste chaînée.
Les listes chaînées font partie de la catégorie des structures de données linéaires. Les éléments composant ce type de structure de données sont ordonnancés de façon séquentielle. On y retrouve également les tableaux, les files ou encore les piles.
Une liste chaînée est composée de nœuds ayant chacun, en plus de la valeur à stocker, un pointeur vers le nœud suivant. On appelle communément le premier nœud head et le dernier nœud tail.
Ce type de listes chaînées est appelé une liste simplement chaînée (ou unidirectionnelle), mais il en existe d’autres comme les listes doublement chaînées (ou bidirectionnelles) ou encore les listes circulaires.
Les différences avec un tableau
Avant de voir l’implémentation d’une liste chaînée et les différents algorithmes associés, il est bon de rappeler quelles sont les différences avec un tableau.
Une histoire de mémoire
La première différence entre une liste chaînée et un tableau se situe au niveau de la représentation des données en mémoire.
Représentation mémoire d’un tableau
Pour rappel, un tableau est une structure de données composée d’un nombre fini d’éléments de même type, stockés en mémoire de façon contiguë (c’est-à-dire les uns après les autres) et pouvant être récupérés via un index.
On peut représenter un tableau en mémoire comme ceci :
Certains d’entre vous se demandent peut-être pourquoi l’adresse mémoire est incrémentée de 4. La réponse est toute simple, le tableau contient des entiers qui occupent 4 octets en mémoire, chaque adresse mémoire d’un élément est donc incrémentée de 4 par rapport à l’adresse du précédent élément.
J’ai dit précédemment que les éléments composant un tableau sont de même type, ce point est très important, car c’est ce qui permet d’accéder aux éléments du tableau via leurs index.
En effet, on vient de voir dans notre exemple, que chaque élément occupe 4 octets en mémoire, en connaissant l’adresse de début du tableau nous pouvons déterminer l’adresse de l’élément se trouvant à l’index i :
Adresse de l'élément en index i = adresse de début + (i * taille d'un élément en octet)
Si l’on souhaite accéder à l’élément se trouvant à l’index 2, son adresse mémoire est donc 1000 + (2 * 4) soit 1008.
Si les éléments étaient de type différent, il aurait été impossible de déterminer les adresses mémoires de ceux-ci.
Comme je l’ai également dit, la taille d’un tableau est statique c’est-à-dire qu’une fois celle-ci définit il n’est plus possible de la modifier. Lors de sa création, le tableau ne contient pas obligatoirement de données, celles-ci pourront être ajoutées par la suite. C’est uniquement sa taille qui doit être connue pour permettre d’allouer la mémoire nécessaire.
Note : Si vous venez de langages de haut niveau tel que JavaScript par exemple, vous êtes sûrement en train de vous dire que c’est tout à fait possible de stocker des éléments de types différents dans un tableau et vous avez raison, mais la représentation d’un tableau en JavaScript est différente de celle-ci, puisqu’un tableau est simplement un objet. Il est également possible d’avoir un tableau de taille dynamique dans la plupart des langages, mais généralement modifier la taille d’un tableau est une opération coûteuse.
Représentation mémoire d’une liste chaînée
Contrairement aux tableaux, il est possible d’ajouter des éléments dans une liste chaînée de façon dynamique. Cela est possible par le fait que les données ne sont pas stockées en mémoire de façon contiguë, mais sont plutôt dispersées comme le montre le schéma suivant :
Par contre, une liste chaînée occupe plus de mémoire qu’un tableau du fait des données supplémentaires qu’elle contient notamment le pointeur vers le nœud suivant (next) ou le nœud précédent (prev) dans le cas d’une liste bidirectionnelle.
Sans rentrer dans les détails, sachez qu’un tableau est plus “cache friendly” qu’une liste chaînée du fait que ses données sont stockées de façon contiguë en mémoire.
Les opérations
Voyons voir maintenant les différences sur les quatre opérations de bases à savoir :
- L’accès à une donnée ;
- La recherche d’une donnée
- L’insertion d’une donnée ;
- La suppression d’une donnée.
L’accès à une donnée
Le tableau
Chaque élément d’un tableau, peut-être accédé en temps constant. Si l’on utilise la notation Big O, on le note O(1). Cela s’explique par le fait que l’on utilise l’index pour accéder à la donnée et que l’adresse mémoire de celle-ci est calculée via cet index comme nous l’avons vu plus haut.
La liste chaînée
Accéder à un nœud particulier d’une liste chaînée nécessite cette fois-ci de parcourir celle-ci en partant du premier nœud jusqu’au nœud voulu. Son temps d’exécution est linéaire et dépend donc de la taille de la liste chaînée, on le note O(n).
La recherche d’une donnée
La recherche d’une donnée dans un tableau ou dans une liste chaînée ne peut être effectuée qu’en temps linaire O(n) puisque nous devons parcourir chaque élément à la recherche de celui qui nous intéresse.
L’insertion d’une donnée
Le tableau
Nous pouvons considérer deux types d’insertions :
- Insertion en début de tableau ;
- Insertion en fin de tableau ;
L’insertion en début de tableau ne peut être réalisée qu’en temps linéaire O(n), pourquoi ? Tout simplement parce que cette opération implique de déplacer les éléments existants vers la droite pour insérer le nouvel élément.
L’insertion en fin de tableau peut quant à elle être effectuée en temps constant O(1), car il n’est pas nécessaire de déplacer les autres éléments. Par contre si le tableau est plein, il sera nécessaire de copier les éléments dans un tableau plus grand, qui ne peut cette fois-ci être effectué qu’en temps linéaire O(n), car il est nécessaire de copier chacune des valeurs dans le nouveau tableau.
La liste chaînée
L’insertion en début de liste chaînée est très simple. Nous connaissons le premier nœud (head), nous avons donc juste à créer un nouveau nœud (qui deviendra le nœud head) et faire pointer sa valeur next sur l’ancien premier nœud (head). Cette opération ne dépend pas de la taille de la liste, elle est donc réalisée en temps constant O(1).
Pour l’insertion en fin de liste c’est la même chose, nous connaissons le dernier nœud (tail), nous avons donc juste à créer un nouveau nœud et changer la valeur next du dernier nœud (tail) pour le faire pointer vers celui que nous venons de créer.
Suppression d’une donnée
Le tableau
La suppression d’un élément d’un tableau ne peut être réalisée en temps constant O(1) que pour le dernier élément, la suppression de tout autre élément implique d’effectuer un décalage des autres éléments vers la gauche et ne peut donc être réalisée qu’en temps linéaire O(n).
La liste chaînée
La suppression d’un nœud d’une liste chaînée nécessite de connaître le nœud précédent à celui que nous souhaitons supprimer et d’affecter la valeur next de ce précédent nœud avec la valeur next de l’élément à supprimer. On trouve dans la littérature que cette opération est réalisable en temps constant O(1) ce qui est vrai en soi, mais cela ne prend pas en compte la recherche du nœud à supprimer qui elle est en temps linéaire O(n)
Quand utiliser une liste chaînée ?
Pour répondre à cette question, voyons voir les avantages et les inconvénients des tableaux et des listes chaînées.
| Tableau | Liste chaînée | |
|---|---|---|
| Avantages | - Accès direct à un élément via son index - Cache friendly - Moins gourmand en mémoire | - Insertion / suppression rapide - Taille dynamique - Allocation de la mémoire uniquement quand on en a besoin |
| Inconvénients | - Insertion / suppression lente - Obligation d'allouer de la mémoire nécessaire lors de la création même si dans le futur celle-ci n'est pas utilisée - La taille est fixe | - L'accès à un nœud nécessite de parcourir la liste - Consommation mémoire plus importante du fait de valeur supplémentaire (next) |
Si vous avez besoin d’ajouter ou supprimer régulièrement des données de façon dynamique sans avoir besoin d’accéder à celles-ci de façon directe (en temps constant O(1)), il est préférable d’utiliser une liste chaînée plutôt qu’un tableau.
Les listes chaînées sont par exemple utilisées pour implémenter les files, les piles ou encore pour l’implémentation des graphes comme nous le verront dans un prochain article.
L’implémentation
Après cette longue introduction théorique, il est temps de passer aux choses concrètes avec l’implémentation d’une liste chaînée.
Avant de continuer, je vous recommande fortement de vous creuser les méninges et d’implémenter vous-même une liste chaînée.
Il peut vous être demandé en entretien d’implémenter celle-ci avec les opérations basiques suivantes :
- L’insertion d’un nœud en début de liste ;
- L’insertion d’un nœud en fin de liste ;
- La suppression d’un nœud ;
- La recherche d’une valeur.
Sachez qu’en entretien vous ne serez pas forcément devant votre IDE favori, mais plutôt face à un tableau blanc (virtuelle ou non) où vous devrez expliquer votre démarche et votre réflexion. Donc, prenez une feuille et un crayon et allez vous poser dans un endroit calme loin de votre ordinateur pour réfléchir à l’implémentation.
Faites des schémas, écrivez du pseudo-code bref posé votre réflexion sur papier. Une fois terminé, vous pourrez reprendre la lecture de l’article.
Bon si vous êtes là c’est que vous avez sûrement terminé ou alors que vous n’avez pas joué le jeu, dans ce cas tant pis pour vous.
Bref, voyons donc comment implémenter une liste chaînée. Créons tout d’abord une classe LinkedListNode représentant un nœud :
1 2 3 4 5 6 | class LinkedListNode { constructor (value, next = null) { this.value = value this.next = next } } |
Puis créons une classe LinkedList :
1 2 3 4 5 6 | class LinkedList { constructor () { this.head = null this.tail = null } } |
Ici head et tail sont deux pointeurs vers des instances de la classe LinkedListNode qui représentent respectivement le début et la fin de la liste chaînée.
Commençons tout d’abord par l’insertion d’un nœud en début de liste :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | prepend (value) { /* On crée un nouveau nœud qui sera le nouveau premier nœud de la liste. L'ancien premier nœud sera quant à lui le nœud suivant. */ this.head = new LinkedListNode(value, this.head) /* S'il n'existe pas encore de nœud dans la liste (ie si c'est le premier nœud qu'on ajoute) on assigne la valeur pointeur du dernier nœud vers le nouveau créé */ if (!this.tail) { this.tail = this.head } return this } |
Voyons ensuite l’insertion en fin de liste :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | append (value) { /* On crée le nouveau nœud, sa valeur next est à null car il s'agit du dernier nœud */ const newNode = new LinkedListNode(value, null) /* Si la liste est vide, il s'agit à la fois du premier et du dernier noeud */ if (!this.head) { this.head = newNode this.tail = newNode return this } /* Sinon le dernier nœud devient maintenant l'avant-dernier nœud et sa valeur * next pointe vers le nouveau nœud */ let currentTail = this.tail currentTail.next = newNode /* On assigne le pointeur du dernier nœud vers le nouveau créé */ this.tail = newNode return this } |
Poursuivons avec la suppression d’un nœud :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | deleteNode (nodeToRemove) { /* Si la liste est vide il n'y a aucun nœud à supprimer */ if (!this.head) { return this } /* Si le nœud à supprimer est le premier nœud ... */ if (this.head === nodeToRemove) { /* On vérifie s'il y a qu'un seul nœud dans la liste ... */ if (!this.head.next) { /* Si c'est le cas la liste est maintenant vide */ this.head = null this.tail = null } else { /* sinon le premier nœud devient le nœud suivant */ this.head = this.head.next } return this } /* On sauvegarde le nœud précédemment, il s'agit du premier nœud * que nous venons déjà de vérifier */ let previousNode = this.head while (previousNode.next) { /* et on vérifie que le nœud suivant est celui que l'on souhaite supprimer */ if (previousNode.next === nodeToRemove) { /* Si c'est le cas le nœud suivant notre nœud précédent est le nœud qui suit celui que nous souhaitons supprimer */ previousNode.next = previousNode.next.next break } previousNode = previousNode.next } /* Avant de finir on vérifie tout de même que le nœud à supprimer n'est pas le dernier nœud si c'est le cas nous devons assigner le pointeur tail vers le précédent nœud qui devient ainsi le dernier nœud */ if (this.tail === nodeToRemove) { this.tail = previousNode } return this } |
C’était un peu plus complexe, mais rien de bien méchant. Je vous donne en bonus le code de la suppression du premier et du dernier élément de la liste :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | deleteHead () { if (!this.head) { return this } if (!this.head.next) { this.head = null this.tail = null return this } this.head = this.head.next return this } deleteTail () { if (this.tail === this.head) { this.tail = null this.head = null return this } let currentNode = this.head while (currentNode.next) { if (!currentNode.next.next) { currentNode.next = null } else { currentNode = currentNode.next } } this.tail = currentNode return this } |
Terminons avec la recherche d’un nœud ayant une valeur spécifique :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | find (value) { if (!this.head) { return null } let currentNode = this.head while (currentNode) { if (currentNode.value === value) { return currentNode } currentNode = currentNode.next } return null } |
Rien de plus simple on parcourt un à un les nœuds à la recherche de notre valeur.
Passons aux choses sérieuses !
Nous venons de voir les bases concernant les listes chaînées, il est temps de passer aux choses sérieuses en s’attaquant aux algorithmes susceptibles d’être posés en entretien. Eh oui ! Ne pensez pas que l’on va uniquement vous demander d’implémenter une liste chaînée avec les opérations de bases, ça serait trop facile !
Il existe plusieurs algorithmes concernant les listes chaînées susceptibles d’être demandés en entretien. Nous n’allons pas tous les voir sinon cet article serait bien trop long. Nous allons seulement nous intéresser à :
- Inverser une liste chaînée ;
- Trouver le milieu d’une liste chaînée ;
- Vérifier si une liste chaînée est cyclique ;
- Retourner le nœud de départ de cycle d’une liste chaînée cyclique ;
- Supprimer le kième élément en partant de la fin ;
- Additionner deux nombres représentés par une liste chaînée.
Comme pour l’implémentation de la liste chaînée, essayez de réfléchir à l’implémentation de ces algorithmes, n’allez pas voir directement la solution, ça ne vous aidera pas. Vous devez réfléchir par vous-même et prendre le temps de trouver une solution.
Ne vous prenez pas la tête à essayer d’avoir une solution optimale dès le début, commencer par résoudre simplement le problème pour ensuite voir si vous pouvez améliorer votre solution.
Posez votre réflexion sur papier, schématisez les problèmes, écrivez du pseudo-code et prenez des exemples sur lesquels appliquer votre solution.
Si vous êtes débutant, je vous recommande grandement la lecture de cet article pour comprendre la méthode de résolution d’un problème d’algorithmique.
Comme je suis sympa, je vous ai préparé une petite sandbox pour pouvoir tester votre code.
Inverser une liste chaînée
Ce premier problème consistant à inverser une liste chaînée est un grand classique.
Nous allons voir deux solutions, la première itérative et la seconde récursive.
La solution itérative
L’algorithme est simple, le nœud qui précède le nœud courant devient le nœud suivant. Rien de mieux qu’un petit schéma pour comprendre :
Ce qui nous donne le code suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | function reverse (linkedList) { let current = linkedList.head let next = null let previous = null while (current) { next = current.next current.next = previous previous = current current = next } linkedList.tail = linkedList.head linkedList.head = previous return linkedList } |
La complexité temporelle est O(n) et la complexité spatiale (c’est-à-dire l’espace mémoire utilisé en fonction de la taille n de l’entrée) est O(1).
La solution récursive
La solution récursive suit le même raisonnement que la fonction itérative. Elle supprime simplement la boucle while par les appels récursifs.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function helper (current, previous) { if (!current) { return previous } const next = current.next current.next = previous return helper(next, current) } function reverse (linkedList) { linkedList.tail = linkedList.head linkedList.head = helper(linkedList.head, null) return linkedList } |
La complexité temporelle est O(n) et la complexité spatiale est également O(n) du fait de la récursivité (ce qui n’est pas vrai pour tous les langages, tout dépend de l’optimisation effectuée par les compilateurs, mais on en reparlera lorsqu’on abordera la récursivité).
Trouver le milieu d’une liste chaînée
Trouver le milieu d’une liste chaînée n’est pas bien compliqué, nous allons voir deux solutions à ce problème, une première solution naïve et une seconde optimisée.
La solution naïve
La première solution qui nous vient en tête consiste à parcourir la liste chaînée pour connaître sa taille permettant de calculer la position du milieu puis de parcourir à nouveau la liste pour s’arrêter dès que l’on a atteint la position du milieu.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function getMiddle (linkedList { let length = 0 let currentNode = linkedList.head while (currentNode) { currentNode = currentNode.next length++ } let middlePosition = Math.floor(length / 2) let middleNode = linkedList.head for (let i = 0; i < middlePosition; i++) { middleNode = middleNode.next } return middleNode } |
Pour information la complexité temporelle de cette solution est O(n + n / 2) puisque l’on parcourt une fois tous les n nœuds puis la moitié soit n / 2. La complexité spatiale est quant à elle O(1).
Note : Généralement, on ne garde que la valeur la plus significative pour la complexité. Dans le cas de notre solution précédente on ne gardera pas le n /2 et on notera la complexité O(n). Mais pour cet article, je préfère vous donner la complexité exacte.
La solution optimisée
On se rend compte dans la première solution que l’on parcourt une première fois la liste puis une seconde fois en s’arrêtant à la moitié de celle-ci. Pourquoi ne pas faire ces deux parcours en même temps. Allez je vous explique.
L’idée est d’avoir deux pointeurs, l’un que l’on va appeler slow et un second que l’on va appeler fast. Nous faisons démarrer les deux au premier nœud (head). Quand le pointeur slow avancera d’un nœud, fast avancera de deux nœuds, fast ira donc deux fois plus “vite”. Quand fast aura atteint la fin de la liste, slow se retrouvera donc au milieu.
Voyons voir le code de cette solution :
1 2 3 4 5 6 7 8 9 10 11 | function getMiddle (linkedList) { let slow = linkedList.head let fast = linkedList.head while (fast && fast.next) { slow = slow.next // On avance de 1 nœud fast = fast.next.next // on avance de 2 nœuds } return slow } |
La complexité temporelle de cet algorithme est O(n). La complexité spatiale est quant à elle O(1).
Vérifier si une liste chaînée est cyclique
Pour ce problème, nous allons également voir deux solutions.
La première solution
La première solution n’est pas bien compliquée, elle consiste à parcourir la liste chaînée et de stocker chaque nœud dans une table de hachage (qui est une structure de données permettant de retrouver une clé en temps constant O(1)). Nous vérifions ensuite pour chaque nœud si celui-ci est présent dans la table de hachage si c’est le cas alors la liste est cyclique. Si nous atteignons la fin de la liste alors celle-ci n’est pas cyclique puisqu’une liste cyclique n’a pas de fin.
Cela se traduit par le code suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function hasCycle (linkedList) { const visitedNodes = new Set() let currentNode = linkedList.head while (currentNode) { if (visitedNodes.has(currentNode)) { return true } visitedNodes.add(currentNode) currentNode = currentNode.next } return false } |
La complexité temporelle de cet algorithme est O(n). Par contre, la complexité spatiale est O(n) puisque nous stockons chaque nœud dans une table de hachage.
Bien que cette solution fonctionne, il peut vous être demandé une solution ayant une complexité spatiale constante c’est-à-dire O(1).
La deuxième solution
La deuxième solution que nous allons voir possède une complexité spatiale constante O(1). Son principe repose sur l’utilisation de deux pointeurs slow et fast comme pour le problème précédent. slow avancera d’un nœud tandis que fast avancera de deux nœuds. Si fast rattrape slow c’est qu’il y a un cycle. Par contre, si fast atteint la fin de la liste c’est qu’il n’y a pas de cycle.
Cette solution s’appelle l’algorithme de détection de cycle de Floyd ou plus simplement l’algorithme du lièvre et de la tortue.
Le code de cet algorithme est le suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function hasCycle (linkedList) { let slow = linkedList.head let fast = linkedList.head while (fast && fast.next) { slow = slow.next fast = fast.next.next if (slow === fast) { return true } } return false } |
La complexité temporelle de cette solution est O(n) et la complexité spatiale O(1).
Retourner le nœud de départ de cycle d’une liste chaînée cyclique
Ce problème peut facilement être résolu en reprenant les solutions du problème précédent.
La première solution
Cette solution est exactement la même que la première solution concernant la détection de cycle. Il suffit de stocker chaque nœud visité dans une table de hachage et de vérifier si le nœud courant est présent dans la table de hachage. Si c’est le cas, on renvoie ce nœud. Par contre si l’on atteint la fin de la liste on renvoie null.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | function getStartNodeOfCycle (linkedList) { const visitedNodes = new Set() let currentNode = linkedList.head while (currentNode) { if (visitedNodes.has(currentNode)) { return currentNode } visitedNodes.add(currentNode) currentNode = currentNode.next } return null } |
Comme nous l’avons déjà vu, la complexité temporelle et spatiale de cette solution est O(n).
La deuxième solution
La deuxième solution reprend l’algorithme du lièvre et de la tortue et utilise donc deux pointeurs fast et slow.
Je vais tenter de vous expliquer simplement comment fonctionne cette solution sans rentrer dans des démonstrations mathématiques complexes qui vont vous faire fuir.
Notons x le nombre de nœuds parcourus avant d’arriver au nœud de départ du cycle.
Notons y le nombre de nœuds parcourus depuis le nœud de départ du cycle jusqu’au nœud de rencontre.
Le nombre de nœuds que parcourt le pointeur slow avant le nœud de rencontre est donc x + y nœuds. Ça va ? Vous me suivez ?
Le pointeur fast a parcouru x nœuds avant d’arriver au nœud de départ du cycle. Il a également obligatoirement parcouru y nœuds donc x + y nœuds parcourus. Comme fast fait au moins un tour boucle avant d’arriver au nœud de rencontre il a parcouru une seconde fois y nœuds donc x + 2y nœuds.
Il nous manque un nombre de nœuds z qui correspond au nombre de nœuds parcourus par fast depuis le nœud de rencontre pour aller jusqu’au nœud de départ du cycle.
fast a donc parcouru x + 2y + z nœuds avant le point de rencontre. Voici un schéma pour illustrer ce qu’on vient de voir.
On sait que fast a parcouru deux fois plus de nœuds que slow et que slow a parcouru x + y nœuds donc fast a parcouru 2 * (x + y) nœuds.
Faisons un petit calcul :
x + 2y + z = 2 * (x + y)
x + 2y + z = 2x + 2y
x + z = 2x
z = x
Donc depuis le nœud de rencontre il faut parcourir x nœuds pour atteindre le nœud de départ du cycle. x correspond aussi au nombre de nœuds à parcourir depuis le début de la liste jusqu’au nœud de départ du cycle.
Avec cette information, il est très simple de déterminer le nœud de départ du cycle. Une fois le nœud de rencontre atteint, il suffit de replacer le pointeur slow en début de liste, et faire avancer nœud par nœud slow et fast (donc à la même vitesse) jusqu’au point de rencontre qui sera le nœud de départ du cycle.
Ce qui nous donne l’algorithme suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function getStartNodeOfCycle (linkedList) { let slow = linkedList.head let fast = linkedList.head while (fast && fast.next && fast.next.next) { slow = slow.next fast = fast.next.next if (slow === fast) { slow = linkedList.head while (slow !== fast) { slow = slow.next fast = fast.next } return slow } } return null } |
La complexité temporelle est O(n) et la complexité spatiale est O(1).
J’espère que vous avez compris le raisonnement, j’ai essayé de simplifier au maximum pour ne pas rentrer dans des formules mathématiques trop complexes (si j’avais parlé de relation de congruence, vous ne seriez déjà plus là).
Supprimer le kième élément en partant de la fin
Pour information, ce problème est posé chez certains géants du web (FAANG). Il s’agit de supprimer le kième nœud d’une liste chaînée en partant du dernier nœud.
Prenons un exemple :
Si k = 1 nous devons supprimer le dernier nœud, si k = 2 l’avant-dernier et ainsi de suite.
Nous allons voir plusieurs solutions à ce problème.
La première solution
La première solution est très simple, elle consiste dans un premier temps à parcourir entièrement la liste afin de connaître sa taille. Puis de parcourir à nouveau la liste à la recherche de la position du nœud à supprimer. Ce nœud se trouve à la position taille - k si l’on considère que le premier nœud (head) se trouve à l’indice 0.
Voyons voir le code de cette solution :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | function removeKthToLast (linkedList, k) { /* Si k égale à 0 ou est négatif on renvoie null */ if (k <= 0) { return null } let runner = linkedList.head let length = 0 /* On calcule la taille de la liste */ while (runner) { runner = runner.next length++ } /* Si k supérieur à la taille de la liste on renvoie null */ if (k > length) { return null } /* On vérifie si c'est le premier nœud que l'on doit supprimer */ if (k === length) { const head = linkedList.head linkedList.head = head.next return head } /* On parcourt la liste jusqu'au nœud à supprimer en prenant soit de mémoriser le nœud précédent */ let previous = null let deletedNode = linkedList.head for (let i = 0; i < length - k; i++) { previous = deletedNode deletedNode = deletedNode.next } /* Si le nœud à supprimer est le dernier il faut veiller à bien affecter le nouveau dernier nœud de la liste au nœud précédent */ if (k === 1) { linkedList.tail = previous } /* On affecte la nouvelle valeur next du nœud précédent avec le nœud suivant du nœud à supprimer */ previous.next = deletedNode.next return deletedNode } |
La complexité temporelle de cette solution est linéaire et vaut O(n + n-k) puisque l’on parcourt une fois la liste chaînée pour connaître sa taille et une seconde fois pour arriver à la position n - k qui est la position du nœud à supprimer. On arrondit généralement cette complexité à O(n). La complexité spatiale est quant à elle constante c’est-à-dire O(1).
La deuxième solution
L’idée de cette solution est d’avoir deux pointeurs runner et previous et de garder une distance de k - 1 nœud entre eux. Pour cela nous commençons par faire avancer le pointeur runner de k nœud.
Nous faisons ensuite avancer le pointeur runner et previous jusqu’à ce que runner atteigne la fin de la liste.
Le pointeur previous se retrouve ainsi sur le nœud qui précède celui que l’on souhaite supprimer. Il ne reste plus qu’à changer le pointeur next du nœud sur lequel pointe previous pour qu’il pointe sur le nœud qui suit celui que l’on souhaite supprimer.
Voici une petite animation pour mieux comprendre :
Le code est le suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | function removeKthToLast (linkedList, k) { /* Si k égale à 0 ou est négatif on renvoie null */ if (k <= 0) { return null } let runner = linkedList.head let previousNode = linkedList.head for (let i = 0; i < k; i++) { /* Si k est plus grand que la taille de la liste on retourne null */ if (!runner) { return null } runner = runner.next } /* On souhaite supprimer le premier nœud */ if (!runner) { const head = linkedList.head linkedList.head = head.next return head } while (runner.next) { runner = runner.next previousNode = previousNode.next } const deletedNode = previousNode.next /* On souhaite supprimer le dernier nœud */ if (!deletedNode.next) { linkedList.tail = previousNode } previousNode.next = deletedNode.next return deletedNode } |
La complexité temporelle de cette solution est O(n - k + k) soit O(n) car nous parcourons la liste jusqu’à la position k puis jusqu’à la fin de la liste. La complexité spatiale est quant à elle toujours constante c’est-à-dire O(1).
Additionner deux nombres représentés par des listes chaînées
Pour ce dernier problème, nous souhaitons additionner deux nombres représentés par des listes chaînées. Les chiffres sont stockés dans l’ordre inverse et chacun des nœuds contient un seul chiffre.
L’idée est assez simple puisqu’elle consiste à poser une addition comme nous avons l’habitude de faire sur papier, mais en commençant par la gauche.
Voici une petite animation pour illustrer la solution :
Le code de cette solution est le suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | function addTwoNumbers (l1, l2) { let currentNodeFirstList = l1.head let currentNodeSecondList = l2.head let currentNodeResult = null const resultList = new LinkedList() let carry = 0 while (currentNodeFirstList != null || currentNodeSecondList != null) { const first = currentNodeFirstList ? currentNodeFirstList.value : 0 const second = currentNodeSecondList ? currentNodeSecondList.value : 0 const sum = carry + first + second carry = Math.floor(sum / 10) const newNode = new LinkedListNode(sum % 10) if (!currentNodeResult) { resultList.head = newNode currentNodeResult = newNode } else { currentNodeResult.next = newNode currentNodeResult = currentNodeResult.next } if (currentNodeFirstList != null) { currentNodeFirstList = currentNodeFirstList.next } if (currentNodeSecondList != null) { currentNodeSecondList = currentNodeSecondList.next } resultList.tail = currentNodeResult } if (carry > 0) { currentNodeResult.next = new LinkedListNode(carry) resultList.tail = currentNodeResult.next } return resultList } |
Il est également possible (et plus judicieux) d’utiliser la méthode append de la liste chaînée comme ceci :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | function addTwoNumbers (l1, l2) { let currentNodeFirstList = l1.head; let currentNodeSecondList = l2.head; const resultList = new LinkedList(); let carry = 0; while (currentNodeFirstList != null || currentNodeSecondList != null) { const first = currentNodeFirstList ? currentNodeFirstList.value : 0; const second = currentNodeSecondList ? currentNodeSecondList.value : 0; const sum = carry + first + second; carry = Math.floor(sum / 10); resultList.append(sum % 10); if (currentNodeFirstList != null) { currentNodeFirstList = currentNodeFirstList.next; } if (currentNodeSecondList != null) { currentNodeSecondList = currentNodeSecondList.next; } } if (carry > 0) { resultList.append(carry); } return resultList; } |
La complexité temporelle de cette solution est O(max(m,n)) avec m la taille de première liste et n la taille de la seconde.
La complexité temporelle est de O(max(m,n) +1) car nous créons une liste chaînée résultat qui possède la taille de la plus grande liste plus un nœud en plus correspondant à l’éventuelle retenue.
Pour finir…
Je pense que l’on va s’arrêter là, l’article est déjà bien trop long. Il existe encore d’autres algorithmes liés aux listes chaînées :
- Supprimer les doublons ;
- Vérifier si une liste est un palindrome ;
- Retourner l’intersection de deux listes chaînées ;
- etc.
Je vous laisse le soin de résoudre ces autres problèmes par vous-même. Vous pouvez d’ailleurs les retrouver sur leetcode.
Avant de vous laisser tranquille, je vous donne ce conseil qui peut paraître bête, mais n’apprenez pas par cœur les solutions aux problèmes que l’on vient de rencontrer. Il est très important que vous les compreniez pour pouvoir les retrouver par vous-même, mais surtout les expliquer.
Je suis lead developer dans une boîte spécialisée dans l’univers du streaming/gaming, et en parallèle, je m’éclate en tant que freelance. Passionné par l’écosystème JavaScript, je suis un inconditionnel de Node.js depuis 2011. J’adore échanger sur les nouvelles tendances et partager mon expérience avec les autres développeurs.
Si vous avez envie de papoter, n’hésitez pas à me retrouver sur Twitter, m’envoyer un petit email ou même laisser un commentaire.
