Middle of the Linked List
Vous disposez d’une liste chaînée simple stockée dans deux tableaux de même longueur. Le nœud i contient la valeur values[i] et 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.
Renvoyez la valeur du nœud du milieu. Si la liste contient un nombre pair de nœuds, il y a deux nœuds du milieu ; renvoyez la valeur du second.
Fonction
- valuesinteger-array
- la valeur détenue par chaque nœud
- nextinteger-array
- l’indice du nœud vers lequel chaque nœud pointe, ou -1 pour le dernier nœud
- Renvoieinteger
- la valeur du nœud du milieu, le deuxième nœud du milieu lorsque la longueur est paire
Contraintes
1 ≤ n ≤ 5000, oùnest la longueur devalueset denext.-104 ≤ values[i] ≤ 104- Chaque
next[i]vaut-1ou correspond à l’indice d’un nœud compris entre0etn-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
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Sortie
- 5
- Explication
- En suivant les liens à partir du nœud
0, on obtient les nœuds0, 3, 4, 2, 1, donc la liste est4, 7, 5, 2, 9. Le troisième des cinq est le nœud4, dont la valeur est5. L’entrée du milieu du tableau lui-même,values[2] = 2, correspond à un nœud différent.
- Entrée
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Sortie
- 40
- Explication
- Ici, les nœuds sont stockés dans l’ordre. Avec six nœuds, il y en a deux au milieu,
30et40, et c’est le deuxième qui l’emporte.
- Entrée
- values = [8]next = [-1]
- Sortie
- 8
- Explication
- Une liste composée d’un seul nœud a ce nœud pour milieu.
+13 tests cachés à la soumission
Pour aller plus loin
Peux-tu renvoyer le nœud situé au tiers de la liste en un seul parcours ? À quelle vitesse chaque pointeur avancerait-il, et où t’arrêterais-tu ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Tu ne connais pas la longueur de la liste avant d’en atteindre la fin. Et si deux marcheurs partaient de la tête et que l’un d’eux avançait deux fois plus vite que l’autre ?
Lorsque le marcheur le plus rapide a atteint la fin, le plus lent a parcouru la moitié de la distance : il se trouve donc sur le nœud central. Il ne reste qu’à déterminer quand s’arrêter pour qu’une longueur paire conduise au deuxième nœud central.
Commencez
slowetfastau nœud0. Tant quefastn’est pas-1et quenext[fast]n’est pas-1, avancez slow d’un lien et fast de deux liens. Ensuite, renvoyezvalues[slow].
Solution
Dans un tableau, le milieu se trouve à l’indice n / 2. Une liste chaînée ne vous donne aucun indice : vous ne découvrez sa longueur qu’en parcourant la liste jusqu’à la fin, et vous avez alors déjà dépassé le milieu. Vous pouvez copier la liste dans un tableau, ou d’abord la compter puis la parcourir à nouveau. La solution astucieuse consiste à faire avancer deux pointeurs dans la liste à des vitesses différentes, de sorte que le pointeur lent soit à mi-chemin lorsque le rapide arrive au bout.
Copiez les valeurs dans un tableau
Intuition
Dans ce problème, un pointeur est l’indice d’un nœud. Passer au nœud suivant se fait avec node = next[node], et atteindre -1 signifie que vous êtes arrivé au bout. Dans le premier exemple, le parcours à partir du nœud 0 suit le chemin 0 → 3 → 4 → 2 → 1 → -1.
Le problème avec une liste, c’est qu’on ne peut pas accéder directement à une position. Il suffit donc de la transformer en une structure qui le permet : parcourez la liste une fois et ajoutez chaque valeur à un nouveau tableau au fur et à mesure. Ce tableau contient les valeurs dans l’ordre de la liste : [4, 7, 5, 2, 9] pour le premier exemple, et son milieu se trouve à l’indice length / 2, en utilisant la division entière.
Cet indice donne à lui seul le second élément du milieu lorsque la longueur est paire : six valeurs donnent l’indice 3, soit la quatrième valeur, qui est 40 dans le deuxième exemple. Le parcours coûte O(n) en temps, et la copie nécessite O(n) de mémoire supplémentaire, ce dont les deux approches suivantes se passent.
Algorithme
- Commencez avec un tableau vide et
node = 0. - Tant que
noden’est pas-1, ajoutezvalues[node]et passez ànext[node]. - Retournez l’entrée à l’index
length / 2, arrondi à l’entier inférieur.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Compte, puis marche à mi-chemin
Intuition
Tu n’as pas besoin de toute la copie, seulement de la longueur. Parcours la liste une fois et compte les nœuds. Puis repars de la tête et avance de length / 2 pas, en arrondissant vers le bas. Le nœud où tu t’arrêtes est celui du milieu.
Pourquoi avancer d’autant de pas : après k pas, tu te trouves sur le nœud à la position k, en comptant la tête comme la position 0. Le milieu d’une liste de 5 est à la position 2, et le deuxième milieu d’une liste de 6 est à la position 3 ; dans les deux cas, c’est length / 2. Dans le premier exemple, tu comptes 5, avances de deux pas 0 → 3 → 4, puis lis values[4] = 5.
La mémoire est maintenant de O(1). Le coût est un deuxième parcours de la moitié de la liste, soit 1.5n déplacements au total, ce qui reste O(n).
Algorithme
- Parcourez les nœuds de
0à-1et comptez-les. - Revenez au nœud
0. - Effectuez
node = next[node]exactementcount / 2fois, en arrondissant à l’entier inférieur. - Renvoyez
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Pointeurs rapides et lents
Intuition
Place deux pointeurs sur la tête. À chaque tour, slow avance d’un nœud et fast de deux. Après k tours, slow se trouve à la position k et fast à la position 2k, donc slow a toujours parcouru la moitié de la distance parcourue par fast. Lorsque fast atteint la fin, slow se trouve au milieu, et tu n’as jamais eu besoin de connaître la longueur.
La règle d’arrêt détermine quel milieu tu obtiens. Continue tant que fast est un nœud réel et qu’il a un nœud après lui : fast != -1 et next[fast] != -1. Si la longueur est impaire, fast s’arrête sur le dernier nœud. Si elle est paire, fast dépasse la fin et prend la valeur -1, ce qui fait avancer slow d’un cran supplémentaire jusqu’au second nœud du milieu. Dans le deuxième exemple, slow parcourt 0, 1, 2, 3 tandis que fast parcourt 0, 2, 4, -1, et values[3] vaut 40.
Dans le premier exemple, slow visite les nœuds 0, 3, 4 tandis que fast visite 0, 4, 1 ; le nœud 1 est le dernier, donc la boucle s’arrête avec slow sur le nœud 4 et la réponse 5. Fast effectue environ n déplacements et slow n / 2, en un seul parcours et avec deux entiers en mémoire.
Algorithme
- Définissez
slow = 0etfast = 0. - Tant que
fast != -1etnext[fast] != -1, définissezslow = next[slow]etfast = next[next[fast]]. - Retournez
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Pièges et cas limites
La boucle est courte : les erreurs se situent donc dans le point de départ, le point d’arrêt et la valeur renvoyée.
- Renvoyer
values[n / 2]. Les nœuds ne sont pas stockés dans l’ordre de la liste, donc l’entrée du milieu du tableau correspond généralement à un autre nœud. Dans le premier exemple, cela renvoie2au lieu de5. - Obtenir le premier milieu lorsque la longueur est paire. Une boucle qui s’exécute tant que
next[fast]etnext[next[fast]]sont tous deux valides s’arrête un tour trop tôt et renvoie30au lieu de40dans le deuxième exemple. - Vérifier
next[fast]avantfast != -1. Lorsque la longueur est paire, fast devient-1, et lirenext[-1]provoque une erreur dans la plupart des langages. En Python, cela lit silencieusement la dernière entrée, ce qui est pire. - Parcourir
count / 2 - 1étapes ou arrondir au supérieur dans l’approche par comptage. Comptez la tête comme position0et avancez d’exactementcount / 2étapes, arrondi à l’inférieur. - Renvoyer l’indice du nœud au lieu de sa valeur.
- Oublier le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds à base 0 et lisez
next[node + 1]. Ruby et R réservent le motnext, donc leurs exemples de départ nomment le paramètrenext_.
Questions fréquentes4
Pourquoi les pointeurs rapide et lent trouvent-ils le milieu d’une liste chaînée ?
Les deux partent de la tête, et à chaque tour, le pointeur rapide avance de deux nœuds tandis que le pointeur lent en avance d’un. Après k tours, le pointeur rapide se trouve à la position 2k et le pointeur lent à la position k, soit exactement à mi-chemin. Ainsi, lorsque le pointeur rapide atteint la fin de la liste, le pointeur lent se trouve au milieu.
Quelle est la complexité temporelle et spatiale de la recherche du milieu d’une liste chaînée ?
Les trois approches prennent un temps de O(n), car il est impossible de trouver le milieu sans parcourir environ la moitié de la liste, voire davantage. Copier les valeurs utilise une mémoire supplémentaire de O(n). Le comptage préalable ainsi que les pointeurs rapide et lent utilisent tous deux O(1), et les pointeurs ne nécessitent qu’un seul parcours.
Comment renvoyer le premier nœud central plutôt que le second ?
Modifiez la condition d’arrêt afin que le pointeur rapide s’arrête un tour plus tôt : bouclez tant que next[fast] != -1 et next[next[fast]] != -1. Pour six nœuds, le pointeur lent s’arrête alors à la position 2 au lieu de 3. Dans l’approche par comptage, parcourez (count - 1) / 2 étapes au lieu de count / 2.
Où la technique des pointeurs rapide et lent est-elle également utilisée ?
Les deux mêmes vitesses permettent de détecter un cycle dans une liste chaînée : dans une boucle, le pointeur rapide rattrape le pointeur lent et ils se rencontrent. Elles permettent aussi de trouver où commence un cycle et de diviser une liste en deux pour le tri fusion ou pour vérifier si une liste se lit de la même façon dans les deux sens.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def middleNode(values, next):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Attendu
5