Sort List
Se te proporciona una lista enlazada simple almacenada en dos arreglos de la misma longitud. El nodo i contiene el valor values[i] y enlaza con el 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, y los arreglos también pueden contener nodos sobrantes a los que nunca se llega al recorrer la lista desde el nodo 0. Esos nodos no forman parte de la lista, incluso cuando sus enlaces apuntan a ella.
Ordena la lista de forma no decreciente según el valor y devuelve los valores de sus nodos en ese orden.
Función
- nextinteger-array
- el índice del nodo al que enlaza cada nodo, o -1 para el último nodo
- valuesinteger-array
- el valor que contiene cada nodo
- Devuelveinteger-array
- los valores de los nodos de la lista, de menor a mayor
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 llega a-1sin visitar dos veces ningún nodo. - Los nodos a los que no llega el recorrido desde el nodo
0no forman parte de la lista. Sus entradasnextpueden apuntar a cualquier lugar.
Ejemplos
- Entrada
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- Salida
- [1, 2, 3, 4, 5]
- Explicación
- El recorrido desde el nodo
0visita los nodos0, 3, 2, 4, 1, así que la lista queda4, 2, 3, 5, 1. Ordenada, queda1, 2, 3, 4, 5.
- Entrada
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- Salida
- [-2, 6]
- Explicación
- La lista es
0 → 2, que se lee6, -2. Nunca se llega a los nodos1y3desde la cabeza, así que se omiten sus valores9y5, aunque el nodo1apunta al nodo0.
- Entrada
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- Salida
- [-1, -1, 3, 3]
- Explicación
- La lista es
3, -1, 3, -1. Los valores iguales se mantienen en la respuesta tantas veces como aparezcan:-1, -1, 3, 3.
Para ir más allá
¿Puedes ordenar volviendo a enlazar los nodos en O(n log n) tiempo, sin copiar los valores?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Qué algoritmos de ordenación necesitan saltar a una posición arbitraria y cuáles solo recorren su entrada avanzando? Una lista enlazada es buena para el segundo tipo.
Fusionar dos listas ordenadas en una sola no requiere memoria adicional: vuelves a enlazar los nodos, tomando siempre el menor de los dos valores iniciales. Si pudieras dividir la lista en dos mitades ordenadas, una fusión bastaría para terminar el trabajo.
Encuentra el punto medio con un puntero lento y otro rápido, y corta la lista ahí. Ordena cada mitad de la misma manera, deteniéndote en un único nodo, que ya está ordenado. Después, combina las dos mitades ordenadas y devuelve la nueva cabeza.
Solución
Quicksort y heapsort dependen del acceso aleatorio, y una lista enlazada simple solo avanza. La ordenación por mezcla es adecuada: dividir una lista por la mitad y combinar dos listas ordenadas implica avanzar en ambas, así que ordena los enlaces mismos en O(n log n). Aquí, n es la longitud de los arreglos.
Copie los valores en un arreglo y ordénelos
Intuición
La lista es lo que recorre node = next[node] desde el nodo 0 hasta -1. Recopila esos valores en un array nuevo, ordénalo con la función de ordenación integrada y devuélvelo. No puedes ordenar values directamente: en el segundo ejemplo contiene 9 y 5, que no están en la lista.
El recorrido es O(n) y la ordenación, O(n log n), con O(n) de memoria adicional. La lista en sí nunca se modifica, por eso los entrevistadores preguntan por el siguiente enfoque.
Algoritmo
- Empieza con un array vacío y
node = 0. - Mientras
nodeno sea-1, añadevalues[node]y avanza anext[node]. - Ordena el array en orden creciente y devuélvelo.
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listOrdenamiento por mezcla en los enlaces
Intuición
Un puntero lento que avanza un enlace y un puntero rápido que avanza dos encuentran el punto medio en un recorrido. Para fusionar dos listas ordenadas, solo se necesitan sus nodos iniciales: toma el menor y avanza al siguiente. Ninguno de los dos pasos necesita un segundo arreglo.
En el primer ejemplo, slow se detiene en el 3, y cortar su enlace divide 4, 2, 3, 5, 1 en 4, 2, 3 y 5, 1. Estas se ordenan como 2, 3, 4 y 1, 5, y la fusión toma 1, 2, 3, 4 y después enlaza el 5 restante.
Cada nivel de división recorre cada nodo un número constante de veces, y hay aproximadamente log n niveles, así que el tiempo es O(n log n). La única memoria adicional es la pila de recursión, de unas 12 llamadas de profundidad para 4000 nodos.
Algoritmo
- Si la lista tiene un nodo (
next[head] == -1), devuelvehead. - Inicia
slow = headyfast = next[head]; avanzaslowun enlace yfastdos mientrasfastynext[fast]no sean-1. - Define
second = next[slow]y corta connext[slow] = -1. - Ordena ambas mitades recursivamente. Combínalas: enlaza el nodo inicial más pequeño después de
tailhasta que una mitad esté vacía y, luego, enlaza el resto de la otra. - Recorre desde la cabeza devuelta y recopila los valores.
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
Errores comunes y casos límite
- Ordenar todo el arreglo
values. En el segundo ejemplo se incorporan9y5, que no están en la lista. - Iniciar
fasten la cabeza. Con dos nodos,slowtermina después en el segundo nodo, el corte deja vacía la segunda mitad y la recursión nunca reduce el tamaño. - Olvidar el corte
next[slow] = -1. Entonces, la primera mitad se extiende hasta la segunda y ambas llamadas ordenan listas superpuestas. - Descartar el resto de una mitad cuando la otra se agota. Esos nodos desaparecen del resultado.
- En Lua y R, los arreglos comienzan en 1: mantén los índices de nodo basados en 0 y lee
next[node + 1]. La versión de R copia el arreglo de enlaces una vez, por lo que utiliza O(n) de memoria adicional.
Preguntas frecuentes3
¿Cuál es la mejor manera de ordenar una lista enlazada?
Ordenamiento por mezcla. Dividir por la mitad, ordenar ambas mitades y combinarlas recorren la lista hacia delante, la única dirección que admite una lista simplemente enlazada. Se ejecuta en tiempo O(n log n) y vuelve a enlazar los nodos existentes.
¿Por qué se prefiere el ordenamiento por mezcla al ordenamiento rápido para las listas enlazadas?
Quicksort puede particionar una lista re enlazándola, pero un buen pivote necesita acceso aleatorio, y tomar la cabeza como pivote hace que una lista ordenada cueste O(n²). Merge sort siempre divide por la mitad, así que se mantiene en O(n log n) con cualquier entrada.
¿Puedes ordenar una lista enlazada en tiempo O(n log n) y con memoria O(1)?
Sí, con ordenamiento por mezcla ascendente. Combina ejecuciones vecinas de longitud 1, luego 2 y luego 4, hasta que una ejecución abarque la lista. Hay log n pasadas lineales y la única memoria necesaria son unos pocos índices de nodos.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def sortList(next, values):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
Salida Esperada
[1, 2, 3, 4, 5]