Reverse Linked List

Q: ¿Cómo inviertes una lista enlazada in situ?

Recorre la lista con dos punteros: prev empieza sin valor y node empieza en la cabeza. En cada nodo, guarda el siguiente nodo, apunta su enlace a prev y después avanza prev y node un paso. Cuando node se agote, prev será la cabeza de la lista invertida.

Q: ¿Cuál es la complejidad temporal y espacial de invertir una lista enlazada?

La versión iterativa visita cada nodo una vez, O(n) de tiempo, y mantiene tres punteros, O(1) de espacio adicional. Copiar primero el orden en un array también requiere O(n) de tiempo, pero necesita O(n) de espacio adicional. Una versión recursiva usa O(n) de espacio para la pila de llamadas.

FácilLista enlazada

+10

Recibes una lista enlazada simple almacenada en el array next: el nodo i apunta al nodo next[i], -1 termina 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.

Invierte la lista cambiando la dirección de cada enlace, de modo que el antiguo último nodo se convierta en la cabeza y el nodo 0 se convierta en el último nodo, apuntando a -1. Devuelve el array next actualizado, que tiene la misma longitud que la entrada.

Función

reverseList(next: integer-array) → integer-array

nextinteger-array: el índice del nodo al que se enlaza cada nodo, o -1 para el último nodo
Devuelveinteger-array: el siguiente arreglo de la lista invertida

Restricciones

1 ≤ next.length ≤ 5000
Cada next[i] es -1 o un índice de nodo de 0 a next.length-1.
Empezando 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: next = [1, 2, 3, -1]
Salida: [-1, 0, 1, 2]
Explicación: La lista es 0 → 1 → 2 → 3. Invertida, es 3 → 2 → 1 → 0, así que el nodo 3 enlaza con 2, el nodo 2 con 1, el nodo 1 con 0 y el nodo 0 con -1.

Entrada: next = [2, -1, 3, 1]
Salida: [-1, 3, 0, 2]
Explicación: La lista es 0 → 2 → 3 → 1, y al revés es 1 → 3 → 2 → 0. Escribir cada enlace nuevo en el índice de su nodo da [-1, 3, 0, 2]. Invertir el array en sí daría [1, 3, -1, 2], que no es lo mismo.

Entrada: next = [-1]
Salida: [-1]
Explicación: Un nodo es su propio inverso. Sigue siendo la cabeza y la cola, y todavía enlaza a -1.

+11 pruebas ocultas al enviar

Para ir más allá

¿Puedes invertir solo la parte de la lista entre la posición left y la posición right, y dejar los nodos anteriores y posteriores en su lugar?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Invertir una lista no mueve ningún nodo; invierte cada enlace. El problema es que el enlace de un nodo es la única forma de llegar al resto de la lista, así que en cuanto lo sobrescribes, se pierde todo lo que viene después. Puedes evitar el problema anotando primero el orden o recorriendo la lista una vez con tres punteros que guardan el camino hacia adelante antes de invertir cada enlace.

Escribe el orden y luego vuelve a enlazarlo

Intuición

En este problema, un puntero es el índice de un nodo, y avanzar es node = next[node]. Recorre la lista desde el nodo 0 hasta llegar a -1 y anota todos los nodos por los que pasas. En el segundo ejemplo, el orden es [0, 2, 3, 1].

En la lista invertida, cada nodo apunta al nodo que lo precedía en ese orden: 1 apunta a 3, 3 a 2, 2 a 0. El primer nodo del orden, la antigua cabeza, no tiene ningún nodo antes, así que apunta a -1. Completa un nuevo arreglo con esos enlaces y devuélvelo.

Como cada enlace se escribe en un arreglo nuevo, no se sobrescribe nada mientras aún lo necesitas, lo que hace que sea difícil equivocarse con esta versión. Tarda O(n) y requiere O(n) de memoria adicional para el orden y el nuevo arreglo.

Algoritmo

Recorre desde el nodo 0 hasta -1 y añade cada nodo a order.
Crea un array nuevo de la misma longitud.
Asigna -1 a la entrada de order[0].
Para cada k ≥ 1, asigna order[k-1] a la entrada de order[k].
Devuelve el array nuevo.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Dale la vuelta a los enlaces en una sola pasada

Intuición

Puedes invertir cada enlace en el momento en que llegues a su nodo, si recuerdas de qué nodo vienes. Mantén prev, el nodo que queda detrás de ti, empezando en -1 porque la cabeza anterior se convertirá en el último nodo. En node, el enlace next[node] apunta hacia delante; asígnale prev para que apunte hacia atrás.

Escribir ese valor destruye tu única forma de avanzar, así que guárdalo primero en una tercera variable, after = next[node]. Después invierte el enlace y mueve ambos punteros un paso: prev = node, node = after. En todo momento, los nodos que quedan detrás de ti forman una lista invertida encabezada por prev, y los nodos que quedan delante son el resto sin modificar, que empieza en node. Cuando node llega a -1, se han invertido todos los enlaces y prev es la nueva cabeza.

En el segundo ejemplo, los punteros recorren los nodos 0, 2, 3, 1 y escriben next[0] = -1, next[2] = 0, next[3] = 2 y next[1] = 3. Cada nodo se visita una vez, en tiempo O(n), y la única memoria utilizada son tres enteros, O(1).

Algoritmo

Establece prev = -1 y node = 0.
Mientras node no sea -1, guarda after = next[node].
Establece next[node] = prev.
Continúa: prev = node, después node = after.
Devuelve next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Errores comunes y casos límite

Casi todos los errores aquí tienen que ver con el orden de las tres asignaciones o con los dos extremos de la lista.

Sobrescribir next[node] antes de guardarlo. Después de next[node] = prev, el enlace hacia delante anterior desaparece y el recorrido retrocede en lugar de avanzar al nodo siguiente.
Iniciar prev con algo distinto de -1. La cabeza anterior debe terminar la lista nueva. Iniciarlo con 0 hace que el nodo 0 se enlace consigo mismo.
Invertir el array en lugar de los enlaces. Los nodos no están almacenados en el orden de la lista, y la respuesta mantiene cada nodo en su propio índice; solo cambian los valores. Invertir [2, -1, 3, 1] da [1, 3, -1, 2], no [-1, 3, 0, 2].
Detenerse un nodo antes usando un bucle con next[node] != -1. También hay que invertir el enlace del último nodo, así que el bucle debe continuar mientras node != -1.
Invertir una lista larga mediante recursión. Una lista de 5000 nodos requiere 5000 llamadas anidadas, por encima del límite de 1000 de Python.
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 palabra next, así que en sus soluciones iniciales el parámetro se llama next_.

Preguntas frecuentes4

¿Cómo inviertes una lista enlazada in situ?

Recorre la lista con dos punteros: prev empieza sin valor y node empieza en la cabeza. En cada nodo, guarda el siguiente nodo, apunta su enlace a prev y después avanza prev y node un paso. Cuando node se agote, prev será la cabeza de la lista invertida.

¿Cuál es la complejidad temporal y espacial de invertir una lista enlazada?

La versión iterativa visita cada nodo una vez, O(n) de tiempo, y mantiene tres punteros, O(1) de espacio adicional. Copiar primero el orden en un array también requiere O(n) de tiempo, pero necesita O(n) de espacio adicional. Una versión recursiva usa O(n) de espacio para la pila de llamadas.

¿Puedes invertir una lista enlazada de forma recursiva?

Sí. Invierte todo lo que viene después de la cabeza, luego haz que el antiguo siguiente nodo de la cabeza apunte de vuelta a la cabeza y establece el enlace de la cabeza en nada. Se lee bien, pero realiza una llamada anidada por nodo, así que una lista larga puede desbordar la pila de llamadas. Python se detiene en 1000 llamadas de forma predeterminada, cantidad que supera una lista de 5000 nodos.

¿Por qué invertir una lista enlazada requiere tres punteros?

Para invertir el enlace de un nodo, necesitas el nodo en sí y el nodo anterior, es decir, dos punteros. El tercero contiene el nodo siguiente, porque invertir el enlace borra la única referencia al resto de la lista. Sin él, el recorrido no puede continuar.

Python

def reverseList(next):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

next = [1, 2, 3, -1]

Esperado

[-1, 0, 1, 2]