Reorder List
On vous donne une liste chaînée simplement chaînée 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.
Appelez les nœuds dans l’ordre de la liste L0, L1, ..., Lk. Réordonnez la liste pour obtenir la séquence L0, Lk, L1, Lk-1, L2, Lk-2, ... : le premier nœud, puis le dernier, puis le deuxième, puis l’avant-dernier, et ainsi de suite. Renvoyez les valeurs dans ce nouvel ordre.
Fonction
- nextinteger-array
- l’index 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
- Renvoieinteger-array
- les valeurs dans l’ordre réorganisé de la liste
Contraintes
1 ≤ n ≤ 4000, oùnest la longueur denextet devalues.-1000 ≤ values[i] ≤ 1000- Chaque
next[i]vaut-1ou un indice de 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
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Sortie
- [1, 5, 2, 4, 3]
- Explication
- En suivant les liens depuis le nœud
0, la liste se lit1, 2, 3, 4, 5. Le premier, le dernier, le deuxième et l’avant-dernier donnent1, 5, 2, 4, et la valeur du milieu3vient en dernier.
- Entrée
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Sortie
- [10, 40, 20, 30]
- Explication
- La liste parcourt les nœuds
0, 2, 1, 3et lit10, 20, 30, 40. Le premier et le dernier donnent10, 40, puis la paire intérieure donne20, 30.
- Entrée
- next = [-1]values = [7]
- Sortie
- [7]
- Explication
- Une liste avec un seul nœud n’a rien à déplacer, donc la réponse est
[7].
Pour aller plus loin
Peux-tu réorganiser les liens eux-mêmes avec une mémoire supplémentaire en O(1) ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Écrivez l’ordre cible pour
1, 2, 3, 4, 5, 6. Quels nœuds proviennent de la première moitié de la liste, et dans quel ordre les nœuds de la seconde moitié apparaissent-ils ?La moitié arrière apparaît à l’envers :
6, 5, 4. Si la moitié arrière était inversée, la réponse serait constituée de deux listes fusionnées en prenant un nœud de chacune à tour de rôle.Trouvez le milieu à l’aide d’un pointeur lent qui avance d’un maillon et d’un pointeur rapide qui en avance de deux. Coupez la liste après le milieu, inversez la deuxième partie en retournant ses liens, puis entrelacez les deux parties nœud par nœud.
Solution
Le nouvel ordre alterne entre le début et la fin, mais une liste simplement chaînée ne se parcourt que vers l’avant. Divise le travail en trois opérations classiques sur les listes : trouve le milieu avec des pointeurs lent et rapide, inverse la seconde moitié, puis entrelace les deux moitiés, un nœud à la fois.
Déplacez la queue vers l’avant, un nœud à la fois
Intuition
Un pointeur désigne ici un indice de nœud, et avancer consiste à faire node = next[node]. Après le premier nœud vient le dernier : décroche donc le dernier nœud et insère-le après le nœud courant, puis recommence deux nœuds plus loin. Pour 1, 2, 3, 4, 5, on obtient 1, 5, 2, 3, 4, puis 1, 5, 2, 4, 3. Arrête-toi lorsqu’il reste moins de deux nœuds après le nœud courant.
Trouver le nœud qui précède le dernier nécessite de parcourir la liste jusqu’à la fin à chaque tour. Ces parcours diminuent de deux nœuds par tour, soit environ n²/4 déplacements au total : quatre millions pour 4000 nœuds.
Algorithme
- Définis
cur = 0. - Tant qu’au moins deux nœuds suivent
cur, parcoursbeforedepuiscurjusqu’à ce quenext[next[before]] == -1, de sorte quetail = next[before]soit le dernier nœud. - Détache-le avec
next[before] = -1, puis insère-le :next[tail] = next[cur]etnext[cur] = tail. - Déplace
curversnext[tail]et recommence. - Parcours depuis le nœud
0et recueille les valeurs.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultCopiez les valeurs et lisez depuis les deux extrémités
Intuition
Un tableau atteint son dernier élément en une étape. Copiez les valeurs dans l’ordre de la liste, [1, 2, 3, 4, 5] dans le premier exemple, puis lisez avec lo depuis le début et hi depuis la fin : prenez lo, prenez hi, et déplacez les deux vers l’intérieur tant que lo < hi. Cela donne 1, 5, 2, 4 ; avec une longueur impaire, les deux se rejoignent sur le 3 du milieu, qui est ajouté en dernier.
La complexité est de O(n) en temps et de O(n) en mémoire supplémentaire, et les liens ne changent jamais.
Algorithme
- Partez du nœud
0et ajoutez chaque valeur àinOrder. - Définissez
lo = 0ethicomme étant le dernier indice. - Tant que
lo < hi, ajoutezinOrder[lo]etinOrder[hi], puis augmentezloet diminuezhi. - Si
lo == hi, ajoutez la valeur du milieu.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultTrouver le milieu, inverser la seconde moitié, entrelacer
Intuition
Pour 1, 2, 3, 4, 5, 6, la réponse est 1, 6, 2, 5, 3, 4 : la première moitié 1, 2, 3 dans l’ordre, en alternance avec la seconde moitié 4, 5, 6 lue à l’envers. Il faut donc couper la liste au milieu, inverser la seconde moitié et entrelacer les deux.
slow avance d’un lien tandis que fast en avance de deux ; ainsi, slow s’arrête sur le dernier nœud de la première moitié : le 3, pour les listes de cinq comme de six nœuds. La couper après ce nœud donne un nœud supplémentaire à la première moitié lorsque la longueur est impaire, et ce nœud termine la réponse. L’entrelacement prend à tour de rôle un nœud de chaque moitié jusqu’à épuisement de la seconde moitié.
Chaque nœud est parcouru un nombre constant de fois, avec quelques indices en mémoire. R copie le vecteur des liens à sa première modification ; la mémoire utilisée en R est donc de O(n).
Algorithme
- Déplacez
slowd’un lien etfastde deux liens tant quenext[fast]etnext[next[fast]]ne sont pas égaux à-1. - Définissez
second = next[slow], puisnext[slow] = -1. - Inversez la liste qui commence à
second; sa nouvelle tête estprev. - Entrelacez : tant que
secondn’est pas égal à-1, reliezfirstàsecondetsecondà l’anciennext[first], puis avancez les deux. - Parcourez la liste à partir du nœud
0et recueillez les valeurs.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
Pièges et cas limites
- Ne pas couper la liste après le milieu. Sans
next[slow] = -1, la première moitié pointe toujours vers la seconde moitié et, après l’entrelacement, la liste boucle sur elle-même. - Écraser un lien avant de l’avoir sauvegardé. Lors de l’inversion et de l’entrelacement, lisez d’abord
next[node]dans une variable, sinon le reste de la liste est perdu. - Entrelacer jusqu’à la fin de la première moitié. Avec une longueur impaire, cette boucle s’exécute une fois de plus avec
secondà-1et litnext[-1]. - Lire l’ordre du tableau comme l’ordre de la liste. Dans le premier exemple,
valuesest[1, 3, 5, 2, 4], mais la liste se lit1, 2, 3, 4, 5. - En Lua et en R, les tableaux commencent à 1. Gardez les index des nœuds basés sur 0 et lisez
next[node + 1].
Questions fréquentes3
Pourquoi inverser la seconde moitié de la liste ?
La réponse lit la seconde moitié depuis son dernier nœud jusqu’à son premier, et une liste simplement chaînée ne se parcourt que vers l’avant. Inverser une fois la seconde moitié, en O(n), permet à la fusion de parcourir les deux moitiés vers l’avant.
Quelle est la complexité temporelle de Reorder List ?
La méthode sur place s’exécute en temps O(n) avec une mémoire supplémentaire de O(1) : trouver le milieu, inverser et entrelacer font chacun parcourir chaque nœud un nombre constant de fois. Copier les valeurs dans un tableau prend également un temps de O(n), mais nécessite une mémoire de O(n), et déplacer la queue d’un nœud à la fois prend un temps de O(n²).
Où se trouve le milieu lorsque la liste contient un nombre pair de nœuds ?
Arrête le pointeur lent sur le dernier nœud de la première moitié. Avec six nœuds, les moitiés sont de trois et trois ; avec cinq, elles sont de trois et deux. Le nœud supplémentaire termine alors la réponse, car c’est à cet endroit que l’ordre place la valeur médiane.
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 reorderList(next, values):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Résultat attendu
[1, 5, 2, 4, 3]