Remove Nth Node From End of List
Recibes una lista enlazada simple almacenada en dos arreglos de la misma longitud. El nodo i contiene el valor values[i] y apunta al nodo next[i]; -1 indica el final de la lista, y la cabeza es el nodo 0. Los nodos no están almacenados en el orden de la lista, así que sigue los enlaces.
Elimina el nodo número n contando desde el final de la lista, donde el último nodo es el primero desde el final. Devuelve los valores de los nodos restantes, en el orden de la lista.
Función
- valuesinteger-array
- el valor que contiene cada nodo
- nextinteger-array
- el índice del nodo al que enlaza cada nodo, o -1 para el último nodo
- ninteger
- qué nodo eliminar, contando desde el final, donde 1 es el último nodo
- Devuelveinteger-array
- los valores restantes en el orden de la lista; queda vacía cuando se elimina el único nodo
Restricciones
1 ≤ L ≤ 5000, dondeLes la longitud devaluesy denext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Cada
next[i]es-1o un índice de nodo de0aL-1. - Comenzando en el nodo
0, la lista visita cada nodo exactamente una vez y después llega a-1. No hay ningún ciclo.
Ejemplos
- Entrada
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Salida
- [5, 2, 6, 7]
- Explicación
- Al seguir los enlaces desde el nodo
0, se visitan los nodos0, 2, 4, 1, 3, por lo que la lista es5, 2, 6, 9, 7. El penúltimo nodo es el nodo1, con valor9, y sin él la lista es5, 2, 6, 7. La entrada del arreglovalues[5-2] = 7es el último nodo, no el que se debe eliminar.
- Entrada
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Salida
- [20, 30, 40]
- Explicación
- Cuatro nodos y
n = 4: el cuarto nodo desde el final es la cabeza. La lista ahora empieza en el nodo1y contiene20, 30, 40.
- Entrada
- values = [42]next = [-1]n = 1
- Salida
- []
- Explicación
- El único nodo es tanto la cabeza como el último nodo. Eliminarlo deja una lista vacía, así que la respuesta es
[].
+14 pruebas ocultas al enviar
Para ir más allá
¿Puedes encontrar y desvincular el nodo en una sola pasada, sin contar primero la longitud?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Una lista solo avanza, y el nodo se define por su distancia desde el final. Si conocieras la longitud
L, ¿en qué posición desde el principio estaría? ¿Y el enlace de qué nodo tienes que cambiar para eliminarlo?Puedes medir la distancia hasta el final sin conocer la longitud. Coloca un puntero
nenlaces por delante de otro y muévelos juntos. Cuando el puntero delantero esté en el último nodo, el puntero seguidor estará justo antes del nodo que hay que eliminar.Avanza
fastnveces. Si ahora es-1, la cabeza es el nodo que hay que eliminar, así que la lista empieza ennext[0]. De lo contrario, avanzaslowyfastjuntos mientrasnext[fast] != -1; después, establecenext[slow] = next[next[slow]]. Recorre la lista desde la cabeza y recopila los valores.
Solución
El objetivo se define por su distancia desde el final, pero una lista enlazada simple solo te permite avanzar, y solo sabes dónde está el final cuando llegas a él. Eliminar un nodo también significa situarse en el nodo anterior, porque el enlace de ese nodo es el que cambia. Puedes copiar la lista en un arreglo, o contar sus elementos y recorrerla de nuevo. La solución clásica mantiene dos punteros separados por n enlaces, de modo que, cuando el puntero delantero llega al último nodo, el trasero se encuentra justo antes del objetivo. A continuación, L es el número de nodos.
Copiar los valores en un array
Intuición
En este problema, un puntero es el índice de un nodo. Avanzar es node = next[node], y llegar a -1 significa que has llegado al final. En el primer ejemplo, el recorrido desde el nodo 0 es 0 → 2 → 4 → 1 → 3 → -1.
Contar desde el final es difícil solo porque una lista no tiene posiciones. Así que asígnale posiciones: recórrela una vez y agrega cada valor a un arreglo. Para el primer ejemplo, ese arreglo es [5, 2, 6, 9, 7]. En un arreglo de L valores, el último está en el índice L-1, así que el n-ésimo desde el final está en el índice L-n. En este caso, es 5-2 = 3, el 9. Elimínalo y devuelve [5, 2, 6, 7].
Esto es correcto y se ejecuta en tiempo O(L), pero copia la lista completa y nunca modifica ningún enlace. El objetivo del problema es editar la lista en sí, usando O(1) de memoria adicional, que es lo que hacen los dos enfoques siguientes.
Algoritmo
- Empieza con una matriz vacía y
node = 0. - Mientras
nodeno sea-1, agregavalues[node]y avanza anext[node]. - Elimina la entrada en el índice
length - n. - Devuelve la matriz.
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 orderCuenta los nodos, después desvincúlalos
Intuición
Para eliminar un nodo de una lista, cambias el enlace del nodo anterior para que lo salte: next[prev] = next[next[prev]]. El nodo eliminado sigue estando en los arreglos, pero ningún recorrido desde la cabeza vuelve a llegar a él.
Así que encuentra prev. Cuenta los nodos en un primer recorrido. Si se cuenta la cabeza como posición 0, el objetivo está en la posición L-n y el nodo anterior está en L-n-1, al que llegas desde la cabeza en L-n-1 pasos. En el primer ejemplo, L = 5 y n = 2: dos pasos, 0 → 2 → 4, te llevan al nodo 4, que está enlazado con el nodo 1, el 9. Asignar next[4] = next[1] = 3 hace que la lista sea 5, 2, 6, 7.
Hay un caso en el que no existe un nodo anterior al objetivo: n = L, cuando el objetivo es la cabeza. En ese caso no hace falta volver a enlazar nada. La lista empieza en next[0] en lugar de 0, como en el segundo ejemplo. Después, recorre la lista desde la cabeza para obtener la respuesta. Dos recorridos por la lista cuestan aproximadamente 2L movimientos, y la memoria adicional, aparte de la respuesta, es de unos pocos enteros.
Algoritmo
- Recorre desde el nodo
0hasta-1y cuenta los nodos comoL. - Si
n == L, la nueva cabeza esnext[0]. - De lo contrario, empieza con
preven el nodo0y muéveloL-n-1veces; después, establecenext[prev] = next[next[prev]]. - Recorre desde la cabeza y recopila
values[node]en orden.
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 resultDos punteros separados por n enlaces
Intuición
Puedes medir «n desde el final» sin conocer L. Avanza fast n enlaces mientras slow espera en la cabeza. Después, avanza ambos un enlace a la vez. La distancia se mantiene en n, así que cuando fast está en el último nodo (next[fast] == -1, posición L-1), slow está en la posición L-1-n: el nodo justo antes del objetivo. Una operación next[slow] = next[next[slow]] elimina el objetivo.
Sigue el primer ejemplo. fast da dos pasos: 0 → 2 → 4. Ahora ambos avanzan: slow va a 2 mientras fast va a 1; después, slow va a 4 mientras fast va a 3. El nodo 3 es el último, así que te detienes. next[4] es el nodo 1, el 9, y establecer next[4] = next[1] = 3 lo elimina.
El caso de la cabeza se resuelve por sí solo. Como n ≤ L, fast llega a -1 durante su avance inicial solo cuando n = L, y eso ocurre exactamente cuando la cabeza es el objetivo. Con objetos de nodo, colocarías un nodo ficticio delante de la cabeza para que este caso desapareciera; aquí, la comprobación fast == -1 cumple la misma función. Encontrar y desenlazar requiere una pasada. Escribir la respuesta requiere otro recorrido, que todos los enfoques necesitan.
Algoritmo
- Establece
fast = 0y avanzanveces confast = next[fast]. - Si
fast == -1, la cabeza es el objetivo: la nueva cabeza esnext[0]. - De lo contrario, establece
slow = 0y avanza ambos mientrasnext[fast] != -1. - Establece
next[slow] = next[next[slow]]. - Recorre desde la cabeza y recopila
values[node]en orden.
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
Errores comunes y casos límite
La mayoría de las respuestas incorrectas se deben al lugar donde se detiene el seguidor y al caso en que se elimina la cabeza.
- Eliminar la entrada en el índice de array
L-n. Los nodos no se almacenan en el orden de la lista, así que ese índice suele corresponder a algún otro nodo. En el primer ejemplo,values[3] = 7es el último nodo, no el9. - Detenerse cuando
fast == -1en lugar de cuandonext[fast] == -1. Eso mueveslowun paso de más, hasta el propio objetivo, y en una lista enlazada simple no puedes desvincular un nodo desde el propio nodo. - Olvidar el caso de la cabeza. Cuando
n = L,fastes-1después de su avance inicial, y leernext[fast]provoca un error en la mayoría de los lenguajes. Python leenext[-1]sin quejarse y devuelve una lista incorrecta, lo que es más difícil de detectar. - Desvincular con
next[slow] = next[slow] + 1oslow + 2. Los nodos vecinos en la lista no son vecinos en los arrays; la única forma de llegar al nodo que está después del objetivo esnext[next[slow]]. - Obtener la respuesta empezando por el nodo
0después de eliminar la cabeza. Comienza el recorrido final desde la nueva cabeza. - Olvidar el desplazamiento en Lua y R, donde los arrays empiezan en 1. Mantén los índices de los nodos basados en 0 y lee
next[node + 1]. Ruby y R reservan la palabranext, así que sus soluciones iniciales llamannext_al parámetro.
Preguntas frecuentes4
¿Cómo eliminas el nodo n.º desde el final de una lista enlazada en una sola pasada?
Usa dos punteros con una separación de n. Avanza el primero n nodos, después mueve ambos a la vez hasta que el primero esté en el último nodo. El segundo queda justo antes del nodo que hay que eliminar, así que haces que su enlace apunte más allá de ese nodo. Si el primer puntero se sale de la lista durante su avance inicial, el nodo que hay que eliminar es la cabeza.
¿Por qué las soluciones a este problema usan un nodo ficticio?
Eliminar un nodo significa cambiar el enlace del nodo anterior, y el nodo principal no tiene ningún nodo delante. Un nodo ficticio colocado delante del nodo principal proporciona un predecesor a todos los nodos, incluido el principal, de modo que una sola línea para desvincular cubre todos los casos. La respuesta comienza entonces en el siguiente nodo del nodo ficticio. Comprobar si el puntero inicial llegó al final de la lista después de n pasos permite manejar el mismo caso sin el nodo adicional.
¿Cuál es la complejidad temporal y espacial de eliminar el nodo n.º desde el final?
Se tarda O(L) para una lista de L nodos, ya que tienes que llegar al final para saber dónde está el objetivo. Tanto contar primero como el método de dos punteros usan O(1) de memoria adicional. Copiar los valores en un array usa O(L).
¿La solución de dos punteros es más rápida que contar primero la longitud?
No mucho: ambos son O(L), y los dos punteros juntos siguen haciendo aproximadamente tantos movimientos como lo harían dos recorridos. La verdadera ventaja es que nunca necesitas conocer la longitud de antemano, así que el método también funciona cuando la lista llega como un flujo que solo puedes leer una vez. Eso es lo que suelen pedir los entrevistadores: una sola pasada.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def removeNthFromEnd(values, next, n):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Esperado
[5, 2, 6, 7]