Merge Two Sorted Lists
Recibes dos listas enlazadas simples, cada una almacenada en dos arreglos de la misma longitud. En la primera lista, el nodo i contiene el valor values1[i] y enlaza con el nodo next1[i]. La segunda lista funciona de la misma manera con next2 y values2. En ambas listas, -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.
Los enlaces de cada lista están ordenados de forma no decreciente. Combina las dos en una sola lista ordenada y devuelve sus valores en orden.
Función
- next1integer-array
- el índice del nodo al que enlaza cada nodo de la primera lista, o -1 para su último nodo
- values1integer-array
- el valor que contiene cada nodo de la primera lista
- next2integer-array
- el índice del nodo al que apunta cada nodo de la segunda lista, o -1 para su último nodo
- values2integer-array
- el valor que contiene cada nodo de la segunda lista
- Devuelveinteger-array
- los valores de la lista combinada, en orden
Restricciones
1 ≤ L1 ≤ 2000, dondeL1es la longitud denext1y devalues1.1 ≤ L2 ≤ 2000, dondeL2es la longitud denext2y devalues2.-1000 ≤ values1[i], values2[j] ≤ 1000- Cada entrada de
next1es-1o un índice de nodo de la primera lista, y cada entrada denext2es-1o un índice de nodo de la segunda lista. - Al comenzar en el nodo
0, cada lista visita cada uno de sus nodos exactamente una vez y después llega a-1. No hay ningún ciclo. - A lo largo de sus enlaces, cada lista está ordenada en orden no decreciente.
Ejemplos
- Entrada
- next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
- Salida
- [1, 2, 3, 4, 6, 7, 9]
- Explicación
- Siguiendo los enlaces, la primera lista visita los nodos
0, 2, 1y lee1, 4, 6; la segunda lee2, 3, 7, 9. Tomar el menor de los primeros elementos cada vez da1, 2, 3, 4, 6, 7, 9.
- Entrada
- next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
- Salida
- [-3, 0, 0, 5]
- Explicación
- La primera lista contiene
-3, 0, 5y la segunda es el único valor0. Ambos0permanecen en el resultado, así que tiene cuatro valores.
- Entrada
- next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
- Salida
- [1, 2, 3, 8, 10]
- Explicación
- La segunda lista se lee
1, 2, 3, todos menores que el8que inicia la primera lista. Primero va toda la segunda lista, después8, 10.
Para ir más allá
¿Puedes combinar k listas ordenadas en un tiempo de O(N log k), donde N es el número total de nodos?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Ambas listas ya están ordenadas. ¿Qué dos valores son los únicos candidatos al valor más pequeño de la lista combinada?
Mantén un puntero en el primer nodo sin usar de cada lista. El menor de sus dos valores va a continuación, y solo ese puntero avanza. Cuando se agote una lista, todo lo que queda en la otra ya está ordenado.
Numera los nodos de la segunda lista después de los de la primera, para que un solo arreglo de enlaces abarque ambas, y agrega un nodo ficticio al principio. Mantén un
tailen el último nodo de la lista combinada, apunta su enlace al nodo inicial más pequeño y avanza. Al final, recorre desde el nodo ficticio y recopila los valores.
Solución
Ambas listas están ordenadas, así que el menor valor restante siempre está al principio de una de ellas. Compara los dos primeros valores, enlaza el menor al resultado y avanza en esa lista. Ordenar los N = L1 + L2 valores también funciona, pero ignora ese orden y cuesta O(N log N).
Coloca todos los valores en un array y ordénalo
Intuición
La lista combinada es la versión ordenada de todos los valores N, así que copia ambos arreglos de valores en uno y ordénalo. El orden de los nodos dentro de los arreglos no importa, porque la ordenación coloca cada valor. Con N ≤ 4000 esto es suficientemente rápido, pero ordenar cuesta O(N log N) comparaciones, mientras que una fusión necesita como máximo N-1, y nunca toca un enlace, la habilidad que evalúa este problema.
Algoritmo
- Copia
values1yvalues2en un solo arreglo. - Ordena el arreglo en orden no decreciente.
- Devuélvelo.
def mergeTwoLists(next1, values1, next2, values2):
# Sorting puts every value in its place without following a single link.
return sorted(values1 + values2)Inserta los nodos detrás de una cabeza ficticia
Intuición
Aquí, un puntero es un índice de nodo. Para enlazar los nodos de ambas listas en una sola cadena, asígnales una numeración común: el nodo j de la lista 2 se convierte en el nodo L1+j, y sus enlaces se desplazan de la misma manera. Un nodo ficticio, con el número L1+L2, se coloca al principio del resultado.
Mantén a y b en el primer nodo sin usar de cada lista, y tail al final de la cadena fusionada. En cada paso, enlaza tail con el menor de los nodos iniciales y avanza ese puntero y tail. Cuando se agota una lista, el resto de la otra ya está ordenado y enlazado, así que una asignación lo adjunta. En el primer ejemplo, la lista 2 se convierte en los nodos 3 a 6. Después de los nodos 0, 3, 6, 2, 1, la lista 1 está vacía y link[tail] = 4 adjunta 7, 9.
Cada nodo se enlaza como máximo una vez: tiempo O(N). El arreglo de enlaces compartido requiere O(N) de memoria, mientras que los objetos de nodo no necesitarían ninguna.
Algoritmo
- Construye un arreglo de enlaces:
next1, despuésnext2desplazado enL1(deja-1tal cual) y luego-1para el elemento ficticioL1+L2. Construye los valores correspondientes. - Establece
a = 0,b = L1ytailen el elemento ficticio. - Mientras ni
anibsean-1, enlazatailcon el menor (usaaen caso de empate), avanza ese puntero y muevetailhasta él. - Enlaza
tailcon el que no sea-1, ya seaaob. - Recorre desde
link[dummy]hasta-1y recopila los valores.
def mergeTwoLists(next1, values1, next2, values2):
n1 = len(next1)
n2 = len(next2)
# One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
# dummy that sits in front of the merged list.
link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
value = list(values1) + list(values2)
dummy = n1 + n2
tail = dummy # the last node of the merged list so far
a = 0 # the first unused node of list 1
b = n1 # the first unused node of list 2
while a != -1 and b != -1:
if value[a] <= value[b]:
link[tail] = a # splice a in after the tail
a = link[a]
else:
link[tail] = b # splice b in after the tail
b = link[b]
tail = link[tail]
# One list ran out. The rest of the other one is sorted and linked already.
link[tail] = a if a != -1 else b
merged = []
node = link[dummy]
while node != -1:
merged.append(value[node])
node = link[node]
return merged
Errores comunes y casos límite
- Combinar los arrays en orden de índice. Los nodos se almacenan desordenados, así que
values1no está ordenado: en el primer ejemplo es[1, 6, 4]. Solo el recorrido desde el nodo0está ordenado. - Olvidar los elementos restantes. Cuando se agota una lista, el bucle se detiene, y descartar el resto de la otra lista hace que se pierdan los valores más grandes:
7, 9en el primer ejemplo. - Avanzar el puntero equivocado, o ambos. Solo avanza la lista cuyo nodo tomaste.
- Mezclar las dos numeraciones. El nodo
2de la lista 2 no es el nodo2de la lista 1. Desplaza los índices y enlaces de la lista 2 enL1, y deja-1tal cual.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de combinar dos listas ordenadas?
Es O(L1 + L2): cada comparación coloca un nodo, y ningún nodo se coloca dos veces. Con objetos de nodo, la fusión necesita O(1) de memoria adicional, ya que solo cambia los enlaces. Con los arreglos que se usan aquí, el arreglo de enlaces compartido ocupa O(L1 + L2) de memoria.
¿Por qué usar un nodo ficticio al fusionar listas enlazadas?
Sin él, el primer nodo del resultado necesita código aparte, porque todavía no hay una cola detrás de la cual enlazarlo. El nodo ficticio es una cabeza provisional, así que el primer nodo se enlaza de la misma manera que todos los demás. Al final, devuelves el siguiente nodo del nodo ficticio y el marcador de posición desaparece.
¿Deberías combinar dos listas ordenadas de forma recursiva o iterativa?
La versión recursiva es corta: el nodo inicial más pequeño apunta a la fusión de todo lo demás. Pero usa un marco de pila por nodo, así que una lista de unos pocos miles de nodos puede desbordar la pila en algunos lenguajes. El bucle iterativo con un puntero a la cola hace el mismo trabajo con espacio de pila constante.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def mergeTwoLists(next1, values1, next2, values2):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
next1 = [2, -1, 1] values1 = [1, 6, 4] next2 = [3, 2, -1, 1] values2 = [2, 7, 9, 3]
Salida Esperada
[1, 2, 3, 4, 6, 7, 9]