Remove Nth Node From End of List

Q: Comment supprimer le n-ième nœud à partir de la fin d'une liste chaînée en un seul parcours ?

Utilisez deux pointeurs séparés par un écart de n . Avancez le premier de n nœuds, puis déplacez-les ensemble jusqu’à ce que le premier soit sur le dernier nœud. Le second se trouve alors juste avant le nœud à supprimer : faites pointer son lien au-delà de ce nœud. Si le premier pointeur sort de la liste pendant son avance initiale, le nœud à supprimer est la tête.

Q: Quelle est la complexité temporelle et spatiale de la suppression du n-ième nœud en partant de la fin ?

Il faut un temps de O(L) pour une liste de L nœuds, car tu dois atteindre la fin pour savoir où se trouve la cible. Le comptage préalable et la méthode des deux pointeurs utilisent tous deux une mémoire supplémentaire de O(1) . Copier les valeurs dans un tableau utilise O(L) .

Q: La solution à deux pointeurs est-elle plus rapide que le fait de compter d’abord la longueur ?

Pas de beaucoup : les deux sont en O(L) , et les deux pointeurs effectuent ensemble à peu près autant de déplacements que deux parcours. Le véritable avantage, c’est que tu n’as jamais besoin de connaître la longueur à l’avance, donc cette méthode fonctionne aussi lorsque la liste arrive sous forme de flux que tu ne peux lire qu’une seule fois. C’est généralement ce passage unique que les intervieweurs demandent.

MoyenListe chaînée Deux pointeurs

+10

On vous donne 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.

Supprimez le n-ième nœud en comptant depuis la fin de la liste, où le dernier nœud est le 1er en partant de la fin. Renvoyez les valeurs des nœuds restants, dans l’ordre de la liste.

Fonction

removeNthFromEnd(values: integer-array, next: integer-array, n: integer) → integer-array

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
ninteger: quel nœud supprimer, en comptant à partir de la fin, où 1 désigne le dernier nœud
Renvoieinteger-array: les valeurs restantes dans l’ordre de la liste, vide lorsque le seul nœud est supprimé

Contraintes

1 ≤ L ≤ 5000, où L est la longueur de values et de next.
-100 ≤ values[i] ≤ 100
1 ≤ n ≤ L
Chaque next[i] vaut -1 ou un indice de nœud compris entre 0 et L-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 = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
Sortie: [5, 2, 6, 7]
Explication: En suivant les liens à partir du nœud 0, on visite les nœuds 0, 2, 4, 1, 3, donc la liste se lit 5, 2, 6, 9, 7. L’avant-dernier depuis la fin est le nœud 1, de valeur 9, et sans lui, la liste se lit 5, 2, 6, 7. L’entrée du tableau values[5-2] = 7 correspond au dernier nœud, et non à celui à supprimer.

Entrée: values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
Sortie: [20, 30, 40]
Explication: Quatre nœuds et n = 4 : le 4e nœud à partir de la fin est la tête. La liste commence maintenant au nœud 1 et contient 20, 30, 40.

Entrée: values = [42]next = [-1]n = 1
Sortie: []
Explication: Le seul nœud est à la fois la tête et le dernier nœud. Le supprimer laisse une liste vide, donc la réponse est [].

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu trouver et délier le nœud en un seul parcours, sans en compter d’abord la longueur ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La cible est définie par sa distance depuis la fin, mais une liste simplement chaînée ne permet d'avancer que vers l'avant, et on ne sait où se trouve la fin qu'une fois qu'on l'a atteinte. Supprimer un nœud implique également de se placer sur le nœud qui le précède, car c'est le lien de ce nœud qui change. Tu peux copier la liste dans un tableau, ou la compter puis la parcourir à nouveau. La solution classique maintient deux pointeurs séparés de n liens, de sorte que lorsque le premier atteint le dernier nœud, le second se trouve juste avant la cible. Ci-dessous, L est le nombre de nœuds.

Copiez les valeurs dans un tableau

Intuition

Dans ce problème, un pointeur est un indice de nœud. Avancer revient à faire node = next[node], et atteindre -1 signifie que vous avez dépassé la fin. Dans le premier exemple, le parcours à partir du nœud 0 suit le chemin 0 → 2 → 4 → 1 → 3 → -1.

Compter depuis la fin est difficile uniquement parce qu’une liste n’a pas de positions. Alors, attribuez-lui des positions : parcourez-la une fois et ajoutez chaque valeur à un tableau. Pour le premier exemple, ce tableau est [5, 2, 6, 9, 7]. Dans un tableau de L valeurs, la dernière se trouve à l’indice L-1, donc la n-ième en partant de la fin se trouve à l’indice L-n. Ici, cela donne 5-2 = 3, soit le 9. Supprimez-le et renvoyez [5, 2, 6, 7].

Cette méthode est correcte et s’exécute en temps O(L), mais elle copie toute la liste et ne modifie aucun lien. Le but du problème est de modifier la liste elle-même, avec une mémoire supplémentaire de O(1), ce que font les deux approches suivantes.

Algorithme

Commence avec un tableau vide et node = 0.
Tant que node n’est pas -1, ajoute values[node] et passe à next[node].
Supprime l’entrée à l’index length - n.
Renvoie le tableau.

def removeNthFromEnd(values, next, n):
    # Write the values out in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Counting from the end, the n-th value sits at index len(order) - n.
    del order[len(order) - n]
    return order

Comptez les nœuds, puis déliez-les

Intuition

Pour supprimer un nœud d’une liste, tu modifies le lien du nœud qui le précède pour qu’il le saute : next[prev] = next[next[prev]]. Le nœud supprimé est toujours dans les tableaux, mais aucun parcours à partir de la tête ne l’atteint plus.

Il faut donc trouver prev. Compte les nœuds lors d’un premier parcours. En comptant la tête comme position 0, la cible se trouve à la position L-n et le nœud qui la précède à la position L-n-1, que tu atteins depuis la tête en L-n-1 étapes. Dans le premier exemple, L = 5 et n = 2 : deux étapes 0 → 2 → 4 te mènent au nœud 4, qui est lié au nœud 1, le 9. En définissant next[4] = next[1] = 3, la liste devient 5, 2, 6, 7.

Dans un cas, il n’y a aucun nœud avant la cible : n = L, lorsque la cible est la tête. Il n’y a alors rien à relier. La liste commence à next[0] au lieu de 0, comme dans le deuxième exemple. Parcours ensuite la liste à partir de la tête pour recueillir la réponse. Deux parcours de la liste coûtent environ 2L déplacements, et la mémoire nécessaire en plus de la réponse se limite à quelques entiers.

Algorithme

Parcourez les nœuds de 0 à -1 et comptez-les pour obtenir L.
Si n == L, la nouvelle tête est next[0].
Sinon, démarrez prev au nœud 0 et déplacez-le L-n-1 fois, puis définissez next[prev] = next[next[prev]].
Parcourez la liste à partir de la tête et collectez values[node] dans l’ordre.

def removeNthFromEnd(values, next, n):
    # First pass: count the nodes.
    length = 0
    node = 0
    while node != -1:
        length += 1
        node = next[node]
    head = 0
    if n == length:
        # The node to remove is the head, so the list starts at its second node.
        head = next[0]
    else:
        # Second pass: stop on the node just before position length - n.
        prev = 0
        for _ in range(length - n - 1):
            prev = next[prev]
        next[prev] = next[next[prev]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Deux pointeurs séparés par n liens

Intuition

Tu peux mesurer « n à partir de la fin » sans connaître L. Avance fast de n maillons tandis que slow attend à la tête. Puis avance les deux d’un maillon à la fois. L’écart reste de n, donc lorsque fast se trouve sur le dernier nœud (next[fast] == -1, position L-1), slow se trouve à la position L-1-n : le nœud juste avant la cible. Un next[slow] = next[next[slow]] suffit à retirer la cible.

Suis le premier exemple. fast avance de deux pas : 0 → 2 → 4. Maintenant, les deux avancent : slow va à 2 tandis que fast va à 1, puis slow va à 4 tandis que fast va à 3. Le nœud 3 est le dernier, donc tu t’arrêtes. next[4] est le nœud 1, le 9, et définir next[4] = next[1] = 3 le retire.

Le cas de la tête apparaît de lui-même. Puisque n ≤ L, fast atteint -1 pendant son avance initiale uniquement lorsque n = L, et c’est précisément le cas où la tête est la cible. Avec des objets nœuds, tu placerais un nœud factice devant la tête pour éliminer ce cas ; ici, la vérification fast == -1 fait la même chose. La recherche et le démaillage nécessitent un seul parcours. Écrire le résultat demande un parcours supplémentaire, dont toutes les approches ont besoin.

Algorithme

Définis fast = 0 et avance de n fois avec fast = next[fast].
Si fast == -1, la tête est la cible : la nouvelle tête est next[0].
Sinon, définis slow = 0 et avance les deux tant que next[fast] != -1.
Définis next[slow] = next[next[slow]].
Parcours la liste depuis la tête et collecte values[node] dans l’ordre.

def removeNthFromEnd(values, next, n):
    # Send fast n links ahead of slow.
    fast = 0
    for _ in range(n):
        fast = next[fast]
    head = 0
    if fast == -1:
        # Fast fell off the end, so the list has exactly n nodes: remove the head.
        head = next[0]
    else:
        # Move both, keeping the gap. When fast stands on the last node,
        # slow stands just before the node to remove.
        slow = 0
        while next[fast] != -1:
            slow = next[slow]
            fast = next[fast]
        next[slow] = next[next[slow]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pièges et cas limites

La plupart des mauvaises réponses viennent de l’endroit où le pointeur suiveur s’arrête et du cas où la tête est supprimée.

Supprimer l’entrée à l’indice L-n du tableau. Les nœuds ne sont pas stockés dans l’ordre de la liste, donc cet indice correspond généralement à un autre nœud. Dans le premier exemple, values[3] = 7 est le dernier nœud, et non le 9.
S’arrêter lorsque fast == -1 au lieu de s’arrêter lorsque next[fast] == -1. Cela fait avancer slow d’un pas de trop, jusqu’à la cible elle-même, et dans une liste chaînée simple, on ne peut pas délier un nœud à partir du nœud lui-même.
Oublier le cas de la tête. Lorsque n = L, fast vaut -1 après son avance initiale depuis la tête, et accéder à next[fast] provoque une erreur dans la plupart des langages. Python lit next[-1] sans broncher et renvoie une liste incorrecte, ce qui est plus difficile à repérer.
Délier avec next[slow] = next[slow] + 1 ou slow + 2. Les voisins dans la liste ne sont pas des voisins dans les tableaux ; le seul moyen d’accéder au nœud qui suit la cible est next[next[slow]].
Récupérer la réponse à partir du nœud 0 après la suppression de la tête. Commencez le parcours final à partir de la nouvelle tête.
Oublier le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds à base 0 et accédez à next[node + 1]. Ruby et R réservent le mot next ; dans leurs exemples de départ, le paramètre est donc nommé next_.

Questions fréquentes4

Comment supprimer le n-ième nœud à partir de la fin d'une liste chaînée en un seul parcours ?

Utilisez deux pointeurs séparés par un écart de n. Avancez le premier de n nœuds, puis déplacez-les ensemble jusqu’à ce que le premier soit sur le dernier nœud. Le second se trouve alors juste avant le nœud à supprimer : faites pointer son lien au-delà de ce nœud. Si le premier pointeur sort de la liste pendant son avance initiale, le nœud à supprimer est la tête.

Pourquoi les solutions à ce problème utilisent-elles un nœud factice ?

Supprimer un nœud consiste à modifier le lien du nœud qui le précède, et la tête n’a aucun nœud avant elle. Un nœud factice placé devant la tête donne à chaque nœud, y compris la tête, un prédécesseur, de sorte qu’une seule ligne de suppression du lien couvre tous les cas. La réponse commence alors au nœud suivant le nœud factice. Vérifier si le pointeur de tête a dépassé la liste après n étapes permet de gérer le même cas sans le nœud supplémentaire.

Quelle est la complexité temporelle et spatiale de la suppression du n-ième nœud en partant de la fin ?

Il faut un temps de O(L) pour une liste de L nœuds, car tu dois atteindre la fin pour savoir où se trouve la cible. Le comptage préalable et la méthode des deux pointeurs utilisent tous deux une mémoire supplémentaire de O(1). Copier les valeurs dans un tableau utilise O(L).

La solution à deux pointeurs est-elle plus rapide que le fait de compter d’abord la longueur ?

Pas de beaucoup : les deux sont en O(L), et les deux pointeurs effectuent ensemble à peu près autant de déplacements que deux parcours. Le véritable avantage, c’est que tu n’as jamais besoin de connaître la longueur à l’avance, donc cette méthode fonctionne aussi lorsque la liste arrive sous forme de flux que tu ne peux lire qu’une seule fois. C’est généralement ce passage unique que les intervieweurs demandent.

Python

def removeNthFromEnd(values, next, n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

values = [5, 9, 2, 7, 6]
next = [2, 3, 4, -1, 1]
n = 2

Attendu

[5, 2, 6, 7]

Remove Nth Node From End of List

Fonction

Contraintes

Exemples

Indices

Solution

Copiez les valeurs dans un tableau

Comptez les nœuds, puis déliez-les

Deux pointeurs séparés par n liens

Pièges et cas limites

Questions fréquentes4

Problèmes similaires