Reorder List
Recibes una lista enlazada simple almacenada en dos matrices de la misma longitud. El nodo i contiene el valor values[i] y enlaza con el 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.
Llama a los nodos en el orden de la lista L0, L1, ..., Lk. Reordena la lista para que quede L0, Lk, L1, Lk-1, L2, Lk-2, ...: primero el primer nodo, después el último, después el segundo, después el penúltimo, y así sucesivamente. Devuelve los valores en ese nuevo orden.
Función
- nextinteger-array
- el índice del nodo al que está enlazado cada nodo, o -1 para el último nodo
- valuesinteger-array
- el valor que contiene cada nodo
- Devuelveinteger-array
- los valores en el orden de la lista reordenada
Restricciones
1 ≤ n ≤ 4000, dondenes la longitud denexty devalues.-1000 ≤ values[i] ≤ 1000- Cada
next[i]es-1o un índice de nodo de0an-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 = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Salida
- [1, 5, 2, 4, 3]
- Explicación
- Siguiendo los enlaces desde el nodo
0, la lista se lee1, 2, 3, 4, 5. Primero, último, segundo y penúltimo dan1, 5, 2, 4, y el valor del medio3va al final.
- Entrada
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Salida
- [10, 40, 20, 30]
- Explicación
- La lista visita los nodos
0, 2, 1, 3y lee10, 20, 30, 40. El primero y el último dan10, 40; después, el par interior da20, 30.
- Entrada
- next = [-1]values = [7]
- Salida
- [7]
- Explicación
- Una lista con un nodo no tiene nada que mover, así que la respuesta es
[7].
Para ir más allá
¿Puedes reordenar los enlaces en sí con memoria adicional O(1)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Escribe el orden objetivo para
1, 2, 3, 4, 5, 6. ¿Qué nodos vienen de la mitad delantera de la lista y en qué orden aparecen los nodos de la mitad trasera?La mitad trasera aparece al revés:
6, 5, 4. Si la mitad trasera estuviera invertida, la respuesta serían dos listas fusionadas tomando un nodo de cada una por turnos.Encuentra el medio con un puntero lento que avanza un enlace y un puntero rápido que avanza dos. Corta la lista después del medio, invierte la segunda parte cambiando el sentido de sus enlaces y luego entrelaza las dos partes nodo por nodo.
Solución
El nuevo orden alterna entre el principio y el final, pero una lista enlazada simple solo avanza. Divide la tarea en tres operaciones habituales con listas: encuentra el centro con punteros lento y rápido, invierte la mitad posterior y entrelaza las dos mitades, un nodo a la vez.
Avanza la cola, un nodo a la vez
Intuición
Un puntero aquí es un índice de nodo, y avanzar es node = next[node]. Después del primer nodo viene el último, así que desvincula el último nodo e insértalo después del actual; luego repite dos nodos más adelante. Para 1, 2, 3, 4, 5, eso da 1, 5, 2, 3, 4, después 1, 5, 2, 4, 3. Detente cuando queden menos de dos nodos después del actual.
Encontrar el nodo anterior al último requiere recorrer la lista hasta el final en cada ronda. Los recorridos se acortan en dos nodos por ronda, lo que da aproximadamente n²/4 desplazamientos en total: cuatro millones para 4000 nodos.
Algoritmo
- Establece
cur = 0. - Mientras haya al menos dos nodos después de
cur, avanzabeforedesdecurhasta quenext[next[before]] == -1, de modo quetail = next[before]sea el último nodo. - Desengánchalo con
next[before] = -1y luego insértalo:next[tail] = next[cur]ynext[cur] = tail. - Mueve
curanext[tail]y repite. - Avanza desde el nodo
0y recopila los valores.
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 resultCopia los valores y lee desde ambos extremos
Intuición
Un arreglo llega a su último elemento en un paso. Copia los valores en el orden de la lista, [1, 2, 3, 4, 5] en el primer ejemplo, luego lee con lo desde el principio y con hi desde el final: toma lo, toma hi y mueve ambos hacia el centro mientras lo < hi. Eso da 1, 5, 2, 4; con una longitud impar, ambos llegan al 3 del medio, que va al final.
Eso requiere tiempo O(n) y memoria adicional O(n), y los enlaces nunca cambian.
Algoritmo
- Recorre desde el nodo
0y añade cada valor ainOrder. - Establece
lo = 0yhien el último índice. - Mientras
lo < hi, añadeinOrder[lo]yinOrder[hi], después incrementaloy decrementahi. - Si
lo == hi, añade el valor del medio.
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 resultEncuentra el punto medio, invierte la segunda mitad, entrelaza
Intuición
Para 1, 2, 3, 4, 5, 6, la respuesta es 1, 6, 2, 5, 3, 4: la mitad delantera 1, 2, 3 en orden, alternando con la mitad trasera 4, 5, 6 leída al revés. Así que corta la lista por la mitad, invierte la mitad trasera y entrelázalas.
slow avanza un enlace mientras que fast avanza dos, así que slow se detiene en el último nodo de la mitad delantera: el 3, tanto si hay cinco como seis nodos. Al cortar después de él, la mitad delantera queda con un nodo extra cuando la longitud es impar, y ese nodo queda al final de la respuesta. El entrelazado toma un nodo de cada mitad por turnos hasta que se agota la mitad trasera.
Cada nodo se visita un número constante de veces, usando unos pocos índices de memoria. R copia el vector de enlaces en su primer cambio, así que en R la memoria es O(n).
Algoritmo
- Mueve
slowun enlace yfastdos enlaces mientrasnext[fast]ynext[next[fast]]no sean-1. - Establece
second = next[slow], despuésnext[slow] = -1. - Invierte la lista que comienza en
second; su nueva cabeza esprev. - Intercala: mientras
secondno sea-1, enlazafirstconsecondysecondcon el antiguonext[first], después avanza ambos. - Recorre desde el nodo
0y recopila los valores.
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
Errores comunes y casos límite
- No cortar la lista después de la mitad. Sin
next[slow] = -1, la mitad delantera sigue apuntando a la mitad trasera y, después de entrelazarlas, la lista vuelve sobre sí misma. - Sobrescribir un enlace antes de guardarlo. Al invertir y entrelazar, lee primero
next[node]en una variable o se perderá el resto de la lista. - Entrelazar hasta que termine la mitad delantera. Si la longitud es impar, ese bucle se ejecuta una vez más con
seconden-1y leenext[-1]. - Interpretar el orden del arreglo como el orden de la lista. En el primer ejemplo,
valueses[1, 3, 5, 2, 4], pero la lista se lee1, 2, 3, 4, 5. - En Lua y R, los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 y lee
next[node + 1].
Preguntas frecuentes3
¿Por qué invertir la segunda mitad de la lista?
La respuesta lee la mitad posterior desde su último nodo hasta el primero, y una lista enlazada simple solo avanza. Invertir la mitad posterior una vez, en O(n), permite que la combinación recorra ambas mitades hacia delante.
¿Cuál es la complejidad temporal de Reorder List?
El método in situ se ejecuta en tiempo O(n) con memoria adicional O(1): encontrar el punto medio, invertir y entrelazar recorren cada nodo un número constante de veces. Copiar los valores en un arreglo también requiere tiempo O(n), pero necesita memoria O(n), y avanzar la cola un nodo a la vez requiere O(n²).
¿Dónde está el medio cuando la lista tiene un número par de nodos?
Detén el puntero lento en el último nodo de la mitad delantera. Con seis nodos, las mitades son de tres y tres; con cinco, son de tres y dos. El nodo extra termina entonces la respuesta, que es donde el orden sitúa el valor del medio.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def reorderList(next, values):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Salida Esperada
[1, 5, 2, 4, 3]