Reverse Nodes in k-Group
Une liste chaînée simple est stockée dans deux tableaux de même longueur. Le nœud i contient 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 peuvent être stockés dans n’importe quel ordre : suivez donc les liens, et non l’ordre du tableau.
Inversez la liste par groupes de k nœuds : les k premiers nœuds sont inversés, puis les k suivants, et ainsi de suite. Le dernier groupe, s’il contient moins de k nœuds, conserve son ordre. Renvoyez les valeurs dans le nouvel ordre de la liste.
Fonction
- nextinteger-array
- l’indice du nœud vers lequel chaque nœud pointe, ou -1 pour le dernier nœud
- valuesinteger-array
- la valeur détenue par chaque nœud
- kinteger
- le nombre de nœuds dans chaque groupe à inverser
- Renvoieinteger-array
- les valeurs dans l’ordre de la nouvelle liste
Contraintes
1 ≤ L ≤ 5000, oùLest la longueur denextet devalues.-1000 ≤ values[i] ≤ 10001 ≤ k ≤ L- Chaque
next[i]vaut-1ou un indice de nœud compris entre0etL-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 = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
- Sortie
- [2, 1, 4, 3, 5]
- Explication
- La liste se lit
1, 2, 3, 4, 5(nœuds0, 2, 4, 1, 3). Les paires1, 2et3, 4sont inversées, et5seul est plus court quek = 2, donc il reste à la fin.
- Entrée
- next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
- Sortie
- [30, 20, 10, 60, 50, 40, 70, 80]
- Explication
- La liste contient
10, 20, ..., 80. Les groupes10, 20, 30et40, 50, 60sont inversés.70, 80est plus court quek = 3, donc il conserve son ordre.
- Entrée
- next = [2, -1, 1]values = [7, 9, 3]k = 3
- Sortie
- [9, 3, 7]
- Explication
- Le tableau affiche
7, 9, 3, mais la liste affiche7, 3, 9. Aveckégal à la longueur, toute la liste forme un seul groupe et ressort inversée :9, 3, 7.
Pour aller plus loin
Peux-tu l’écrire de manière récursive, en inversant un groupe et en récursant sur le reste de la liste ? Combien de mémoire supplémentaire cela utilise-t-il ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Inverser une liste entière consiste à parcourir la liste avec deux pointeurs, le nœud précédent et le nœud courant, en inversant chaque lien au fur et à mesure. Qu’est-ce qui change si le parcours doit s’arrêter après
knœuds et que le reste de la liste doit rester attaché ?Avant d’inverser un groupe, avance de
kétapes pour vérifier qu’il existeknœuds ; sinon, laisse le reste tel quel. Le nœud sur lequel tu arrives se trouve juste après le groupe, et le premier nœud du groupe doit finir par pointer vers lui.Conservez le dernier nœud de la partie déjà terminée. Après avoir inversé un groupe, faites pointer ce nœud vers le nouveau premier nœud du groupe (pour le premier groupe, ce nœud est la nouvelle tête). L’ancien premier nœud du groupe est maintenant le dernier nœud de la partie terminée.
Solution
Inverser une liste entière consiste en un seul passage de retournements de liens. Ici, les retournements s’arrêtent tous les k nœuds, et chaque groupe inversé doit être raccordé à la partie qui le précède et aux nœuds qui le suivent. Tu peux copier les valeurs dans un tableau et inverser les blocs, ou relier chaque groupe sur place avec une mémoire supplémentaire en O(1).
Copiez les valeurs et inversez chaque bloc
Intuition
Parcours à partir du nœud 0 avec node = next[node] et copie les valeurs dans un tableau en respectant l’ordre de la liste. Les groupes correspondent maintenant aux blocs d’indices 0 à k-1, k à 2k-1, et ainsi de suite : inverse chaque bloc complet et laisse le dernier bloc, s’il est plus court, tel quel. Cela prend un temps O(L) et une mémoire supplémentaire O(L), sans jamais toucher à un lien.
Algorithme
- Parcourez les nœuds à partir de
0jusqu’à-1et ajoutezvalues[node]à un tableau. - Pour
start = 0, k, 2k, ...tant questart + k ≤ L: inversez le bloc de l’indexstartà l’indexstart+k-1. - Laissez tel quel le bloc plus court à la fin.
- Retournez le tableau.
def reverseKGroup(next, values, k):
# Read the values in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Reverse every full block of k; a shorter last block stays as it is.
for start in range(0, len(order) - k + 1, k):
order[start:start + k] = order[start:start + k][::-1]
return orderInversez chaque groupe sur place en rétablissant les liens
Intuition
Pour inverser une liste entière, on la parcourt avec prev et node, puis on définit next[node] = prev. Un groupe consiste à exécuter la même boucle k fois, avec prev initialisé à after, le nœud situé juste après le groupe. Le premier nœud du groupe devient son dernier nœud et pointe vers after, de sorte que le reste de la liste reste attaché.
Comptez k nœuds avant de les inverser : si vous atteignez d’abord -1, le reste forme un groupe trop court et reste tel quel. Après l’inversion, prev est le nouveau premier nœud du groupe. Reliez le dernier nœud du groupe précédent à celui-ci, ou faites-en la tête de liste pour le premier groupe. L’ancien premier nœud du groupe est maintenant le dernier nœud de la partie traitée.
Chaque nœud est parcouru deux fois, une fois pour le comptage et une fois pour l’inversion : temps O(L) et quelques entiers en mémoire (O(L) en R, qui copie le vecteur de liens lors de sa première modification).
Algorithme
- Commence avec
head = 0,prevTail = -1,groupStart = 0. - Parcours
kétapes depuisgroupStartjusqu’àafter; si tu atteins-1avant, passe à l’étape 5. - Avec
prev = afteretnode = groupStart, répètekfois : enregistrenext[node], définisnext[node] = prev, puis avance les deux. - Si
prevTailvaut-1, définishead = prev; sinon, définisnext[prevTail] = prev. DéfinisprevTail = groupStart,groupStart = after; passe à l’étape 2. - Récupère les valeurs à partir de
head.
def reverseKGroup(next, values, k):
head = 0 # the list's head; changes after the first group
prev_tail = -1 # last node of the groups already reversed
group_start = 0
while True:
# Find the node right after this group, or stop if fewer than k remain.
after, count = group_start, 0
while after != -1 and count < k:
after = next[after]
count += 1
if count < k:
break
# Turn the group's k links around. Its first node ends up last
# and links to the node after the group.
prev, node = after, group_start
for _ in range(k):
following = next[node]
next[node] = prev
prev, node = node, following
# prev is the group's new first node: hang it after the previous group.
if prev_tail == -1:
head = prev
else:
next[prev_tail] = prev
prev_tail = group_start
group_start = after
# Walk the relinked list from its head.
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Pièges et cas limites
- Inverser le dernier groupe incomplet. Comptez
knœuds avant de les inverser ; un lien inversé ne peut pas être rétabli sans un autre parcours. - Commencer l’inversion avec
prev = -1, comme pour une inversion complète. Le dernier groupe incomplet disparaît alors : le premier exemple renvoie2, 1, 4, 3. - Ne pas relier le dernier nœud du groupe précédent au nouveau premier nœud. Il pointe toujours vers l’ancien premier nœud, donc
k-1nœuds disparaissent. - Lire la réponse à partir du nœud
0, ou lirevaluesde gauche à droite. Dès qu’un groupe dek ≥ 2nœuds est inversé, le nœud0n’est plus la tête, et l’ordre du tableau n’a jamais été celui de la liste. - Utiliser un indexage à partir de 0 en Lua et R, dont les tableaux commencent à 1. Gardez les index des nœuds à partir de 0 et lisez
next[node + 1].
Questions fréquentes3
Quelle est la complexité temporelle et spatiale de l’inversion des nœuds par groupes de k ?
Il s’exécute en temps O(L) pour une liste de L nœuds : chaque nœud est compté une fois et inversé une fois. La version en place utilise O(1) mémoire supplémentaire ; copier les valeurs dans un tableau utilise O(L).
Que se passe-t-il pour le dernier groupe s’il contient moins de k nœuds ?
Il conserve son ordre initial. Compte k nœuds avant d’inverser chaque groupe ; si tu atteins d’abord la fin de la liste, laisse le reste tel quel.
Pourquoi les solutions à ce problème utilisent-elles un nœud fictif ?
Avec des objets nœud, un nœud factice placé avant la tête donne au premier groupe un nœud devant lui, de sorte qu’une seule ligne relie chaque groupe à la partie terminée. Avec un tableau de liens, un prevTail qui reste à -1 jusqu’à ce que le premier groupe soit terminé joue le même rôle.
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.
def reverseKGroup(next, values, k):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
next = [2, 3, 4, -1, 1] values = [1, 4, 2, 5, 3] k = 2
Résultat attendu
[2, 1, 4, 3, 5]