Palindrome Linked List
Tu reçois une liste 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, suis donc les liens.
Renvoie true si les valeurs lues de la tête à la fin sont les mêmes que celles lues de la fin vers la tête, et false sinon.
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
- Renvoieboolean
- vrai si la liste se lit de la même façon dans les deux sens
Contraintes
1 ≤ L ≤ 5000, oùLest la longueur denextet devalues.-100 ≤ values[i] ≤ 100- 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 = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- Sortie
- true
- Explication
- Les liens visitent les nœuds
0, 4, 1, 3, 2, donc la liste se lit3, 1, 4, 1, 3. Les deux 3 correspondent, les deux 1 correspondent, et le4au milieu n’a pas de partenaire à vérifier.
- Entrée
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- Sortie
- true
- Explication
- La liste parcourt les nœuds
0, 2, 3, 1et lit4, 9, 9, 4, la même chose dans les deux sens.
- Entrée
- next = [2, -1, 1]values = [1, 2, 1]
- Sortie
- false
- Explication
- Le tableau
valuesest[1, 2, 1], mais la liste parcourt les nœuds0, 2, 1et lit1, 1, 2. À l’envers, cela donne2, 1, 1, donc la réponse estfalse.
Pour aller plus loin
Peux-tu le faire en O(L) avec O(1) mémoire supplémentaire ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
La vérification d’un palindrome compare la première valeur à la dernière, la deuxième à l’avant-dernière, et ainsi de suite. Dans une liste simplement chaînée, tu ne peux avancer que vers l’avant. Qu’est-ce qui permettrait d’accéder à l’arrière ?
Copier les valeurs dans un tableau dans l’ordre de la liste fonctionne, mais cela coûte
O(L)en mémoire. Sans la copie, il faut parcourir la seconde moitié à l’envers. Modifier ses liens peut rendre cela possible.Trouvez le milieu à l’aide de deux pointeurs :
fastavance de deux maillons chaque fois queslowen avance d’un. Lorsquefastne peut plus avancer,slowmarque la fin de la première moitié. Inversez les maillons aprèsslow, puis parcourez la liste à partir de la tête et de l’ancien dernier nœud en même temps et comparez.
Solution
La vérification d’un palindrome associe chaque valeur à son miroir situé à l’autre extrémité. Une liste simplement chaînée ne se parcourt que vers l’avant ; la difficulté consiste donc à lire la seconde moitié à l’envers. Une copie dans un tableau le permet en utilisant une mémoire de O(L), où L est le nombre de nœuds ; inverser les liens de la seconde moitié le permet en utilisant O(1).
Copiez les valeurs dans un tableau
Intuition
Ici, un pointeur est un indice de nœud, et avancer revient à faire node = next[node]. Parcourez la liste une fois et copiez chaque valeur dans un tableau, que vous pouvez lire depuis les deux extrémités. Comparez les première et dernière valeurs, déplacez les deux indices vers le milieu et renvoyez false en cas de différence. Pour une longueur impaire, la valeur du milieu est son propre partenaire.
Il faut lire chaque valeur ; un temps d’exécution en O(L) est donc optimal. Le coût est de L entiers supplémentaires.
Algorithme
- Parcourez les nœuds de
0à-1et ajoutez chaquevalues[node]à un tableau. - Définissez
i = 0etjcomme étant le dernier indice. - Tant que
i < j, renvoyezfalsesi les deux valeurs diffèrent, sinon incrémenteziet décrémentezj. - Renvoyez
true.
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return TrueInverser la seconde moitié sur place
Intuition
Inverse les liens de la seconde moitié au lieu de la copier : un parcours depuis l’ancien dernier nœud mène alors vers le milieu. Pour trouver le milieu, fais avancer fast de deux liens pour chaque lien parcouru par slow, tandis que fast a deux liens d’avance. slow s’arrête sur le dernier nœud de la première moitié, le nœud du milieu lorsque L est impair. Dans le premier exemple, slow parcourt 0 → 4 → 1 tandis que fast parcourt 0 → 1 → 2, donc slow s’arrête sur le 4.
Inverse les nœuds après slow, puis parcours simultanément left depuis la tête et right depuis la moitié inversée : 3 avec 3, puis 1 avec 1. La moitié inversée n’est jamais plus longue que la première moitié ; s’arrêter lorsque right se termine permet donc de comparer exactement les paires pertinentes. Chaque phase parcourt au plus L nœuds et stocke quelques entiers. En R, modifier next_ copie le vecteur une fois, donc R utilise O(L) mémoire.
Algorithme
- Définis
slow = fast = 0. Tant quenext[fast]etnext[next[fast]]ne sont pas tous deux égaux à-1, avanceslowd’un lien etfastde deux. - Inverse la liste qui commence à
next[slow]: pour chaque nœud, sauvegarde son lien, fais-le pointer versprev, puis avanceprevet le nœud. - Définis
left = 0etright = prev, la tête de la moitié inversée. - Tant que
right != -1, renvoiefalseen cas de différence ; sinon, avance les deux pointeurs d’un lien. - Renvoie
true.
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
Pièges et cas limites
- Vérifier les tableaux au lieu de la liste. Dans le troisième exemple,
valuesvaut[1, 2, 1], mais la liste affiche1, 1, 2. - Tester uniquement
next[fast] != -1.fastpeut alors passer à-1et lirenext[-1], ce qui est hors limites dans la plupart des langages et correspond silencieusement à la dernière entrée en Python et en Ruby. - Comparer jusqu’à ce que
leftse termine au lieu deright. Le nœud du milieu pointe toujours vers l’ancienne seconde moitié, donc le parcours depuis la tête est le plus long. - Écraser
next[node]pendant l’inversion avant de l’avoir enregistré, ce qui fait perdre le reste de la liste. - En Lua et en R, où les tableaux commencent à 1, lire
next[node]pour un identifiant de nœud basé sur 0. Lirenext[node + 1].
Questions fréquentes3
Quelle est la complexité temporelle de la vérification d’une liste chaînée palindrome ?
Chaque approche est en O(L) pour une liste de L nœuds, car chaque valeur doit être comparée. Copier les valeurs dans un tableau ou sur une pile utilise O(L) de mémoire supplémentaire ; inverser la seconde moitié sur place utilise O(1).
Comment les pointeurs rapide et lent trouvent-ils le milieu d’une liste chaînée ?
Les deux commencent au début, et le pointeur rapide avance de deux pas pour chaque pas du pointeur lent. Lorsque le pointeur rapide atteint la fin, il a parcouru toute la liste, et le pointeur lent en a parcouru la moitié.
Est-ce qu’inverser la moitié de la liste détruit l’entrée ?
Oui, cela modifie les liens de la seconde moitié, et dans la plupart des langages, ce tableau appartient à l’appelant. Si la liste est toujours nécessaire, terminez la comparaison sans retourner prématurément, puis inversez à nouveau cette moitié. Le nœud du milieu pointe toujours vers le premier nœud de cette moitié, la liste est donc de nouveau complète avec une mémoire supplémentaire en O(1).
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 isPalindrome(next, values):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
Résultat attendu
true