Middle of the Linked List
Recibes una lista simplemente enlazada 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, así que sigue los enlaces.
Devuelve el valor del nodo central. Cuando la lista tiene un número par de nodos, hay dos nodos centrales; devuelve el valor del segundo.
Función
- valuesinteger-array
- el valor almacenado por cada nodo
- nextinteger-array
- el índice del nodo al que se conecta cada nodo, o -1 para el último nodo
- Devuelveinteger
- el valor del nodo central, el segundo nodo central cuando la longitud es par
Restricciones
1 ≤ n ≤ 5000, dondenes la longitud devaluesy denext.-104 ≤ values[i] ≤ 104- 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
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Salida
- 5
- Explicación
- Siguiendo los enlaces desde el nodo
0se obtienen los nodos0, 3, 4, 2, 1, así que la lista queda4, 7, 5, 2, 9. El tercero de los cinco es el nodo4, cuyo valor es5. La entrada central del propio arreglo,values[2] = 2, es un nodo diferente.
- Entrada
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Salida
- 40
- Explicación
- Aquí los nodos se almacenan en orden. Con seis nodos hay dos centrales,
30y40, y gana el segundo.
- Entrada
- values = [8]next = [-1]
- Salida
- 8
- Explicación
- Una lista de un nodo tiene como elemento central ese mismo nodo.
+13 pruebas ocultas al enviar
Para ir más allá
¿Puedes devolver el nodo que está a un tercio del recorrido por la lista en una sola pasada? ¿A qué velocidad se movería cada puntero y dónde te detendrías?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
No sabes la longitud de la lista hasta que llegas al final. ¿Y si dos caminantes empezaran en la cabeza y uno de ellos se moviera el doble de rápido que el otro?
Cuando el caminante más rápido ha llegado al final, el más lento ha recorrido la mitad de la distancia, así que se encuentra en el nodo central. El único detalle que queda es cuándo detenerse para que, si la longitud es par, llegue al segundo nodo central.
Inicia
slowyfasten el nodo0. Mientrasfastno sea-1ynext[fast]no sea-1, avanza slow un enlace y fast dos enlaces. Después, devuelvevalues[slow].
Solución
En un arreglo, el punto medio está en el índice n / 2. Una lista enlazada no tiene índices: solo averiguas cuánto mide al recorrerla hasta el final, y para entonces ya habrás pasado el punto medio. Puedes copiar la lista en un arreglo o contar primero y volver a recorrerla. La solución ingeniosa envía dos punteros por la lista a distintas velocidades, de modo que el lento esté a mitad de camino cuando el rápido llegue al final.
Copia los valores en un arreglo
Intuición
En este problema, un puntero es un índice de nodo. Pasar al siguiente nodo es node = next[node], y llegar a -1 significa que has llegado al final. En el primer ejemplo, el recorrido desde el nodo 0 sigue 0 → 3 → 4 → 2 → 1 → -1.
El problema con una lista es que no puedes saltar a una posición. Así que conviértela en algo que sí te lo permita: recorre la lista una vez y añade cada valor a un nuevo arreglo a medida que avanzas. Ese arreglo contiene los valores en el orden de la lista, [4, 7, 5, 2, 9] en el primer ejemplo, y su centro está en el índice length / 2 usando división entera.
Ese índice da por sí solo el segundo valor central cuando la longitud es par: seis valores dan el índice 3, el cuarto valor, que es 40 en el segundo ejemplo. El recorrido cuesta O(n) de tiempo y la copia cuesta O(n) de memoria adicional, algo que los dos enfoques siguientes evitan.
Algoritmo
- Empieza con un arreglo vacío y
node = 0. - Mientras
nodeno sea-1, agregavalues[node]y avanza anext[node]. - Devuelve la entrada en el índice
length / 2, redondeado hacia abajo.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Cuenta y después camina la mitad del trayecto
Intuición
No necesitas copiar toda la lista, solo conocer su longitud. Recorre la lista una vez y cuenta los nodos. Después, vuelve a empezar desde la cabeza y avanza length / 2 pasos, redondeando hacia abajo. El nodo en el que te detengas es el del medio.
Por qué hay que avanzar esa cantidad de pasos: después de k pasos, estás en el nodo de la posición k, contando la cabeza como la posición 0. El punto medio de una lista de 5 está en la posición 2, y el segundo punto medio de una lista de 6 está en la posición 3; ambos corresponden a length / 2. En el primer ejemplo cuentas 5, avanzas dos pasos 0 → 3 → 4 y lees values[4] = 5.
Ahora la memoria es O(1). El costo es un segundo recorrido por la mitad de la lista, 1.5n movimientos en total, que sigue siendo O(n).
Algoritmo
- Avanza desde el nodo
0hasta-1y cuenta los nodos. - Vuelve al nodo
0. - Ejecuta
node = next[node]exactamentecount / 2veces, redondeando hacia abajo. - Devuelve
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Apuntadores rápidos y lentos
Intuición
Coloca dos punteros en la cabeza. En cada ronda, slow avanza un nodo y fast avanza dos. Después de k rondas, slow estará en la posición k y fast en la posición 2k, así que slow siempre habrá recorrido la mitad de la distancia de fast. Cuando fast llega al final, slow está en el medio, y nunca necesitaste conocer la longitud.
La regla de parada determina cuál de los nodos centrales obtienes. Continúa mientras fast sea un nodo real y tenga un nodo después: fast != -1 y next[fast] != -1. Con una longitud impar, fast se detiene en el último nodo. Con una longitud par, fast sale del final y llega a -1, lo que hace que slow avance un paso más, hasta el segundo nodo central. En el segundo ejemplo, slow avanza por 0, 1, 2, 3, mientras que fast avanza por 0, 2, 4, -1, y values[3] es 40.
En el primer ejemplo, slow visita los nodos 0, 3, 4, mientras que fast visita 0, 4, 1; el nodo 1 es el último, así que el bucle se detiene con slow en el nodo 4 y la respuesta es 5. Fast hace aproximadamente n movimientos y slow n / 2, en una sola pasada y usando dos enteros de memoria.
Algoritmo
- Establece
slow = 0yfast = 0. - Mientras
fast != -1ynext[fast] != -1, estableceslow = next[slow]yfast = next[next[fast]]. - Devuelve
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Errores comunes y casos límite
El bucle es corto, así que los errores están en dónde empieza, dónde termina y qué devuelve.
- Devolver
values[n / 2]. Los nodos no están almacenados en el orden de la lista, así que la entrada central del array suele ser otro nodo. En el primer ejemplo, devuelve2en vez de5. - Obtener el primer nodo central cuando la longitud es par. Un bucle que se ejecuta mientras
next[fast]ynext[next[fast]]sean ambos nodos reales se detiene una iteración antes y devuelve30en vez de40en el segundo ejemplo. - Comprobar
next[fast]antes defast != -1. Cuando la longitud es par, fast pasa a ser-1, y leernext[-1]provoca un error en la mayoría de los lenguajes. En Python, en cambio, lee silenciosamente la última entrada, lo cual es peor. - Avanzar
count / 2 - 1pasos o redondear hacia arriba en el enfoque de conteo. Cuenta la cabeza como la posición0y da exactamentecount / 2pasos, redondeando hacia abajo. - Devolver el índice del nodo en vez de su valor.
- 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
¿Por qué los punteros rápido y lento encuentran el centro de una lista enlazada?
Ambos comienzan en la cabeza, y en cada ronda el puntero rápido avanza dos nodos mientras que el lento avanza uno. Después de k rondas, el puntero rápido está en la posición 2k y el lento en la posición k, exactamente a la mitad. Así que cuando el puntero rápido llega al final de la lista, el lento está en el medio.
¿Cuál es la complejidad temporal y espacial de encontrar el elemento central de una lista enlazada?
Los tres enfoques tardan O(n), ya que no se puede encontrar el elemento central sin recorrer aproximadamente la mitad de la lista o más. Copiar los valores utiliza O(n) de memoria adicional. Contar primero y usar los punteros rápido y lento requieren ambos O(1), y los punteros solo necesitan una pasada.
¿Cómo devuelves el primer nodo central en lugar del segundo?
Cambia la condición de parada para que el puntero rápido se detenga una ronda antes: repite mientras next[fast] != -1 y next[next[fast]] != -1. Para seis nodos, el puntero lento se detiene entonces en la posición 2 en lugar de 3. En el enfoque de conteo, avanza (count - 1) / 2 pasos en lugar de count / 2.
¿En qué otros casos se utiliza la técnica de los punteros rápido y lento?
Las mismas dos velocidades detectan un ciclo en una lista enlazada: en un bucle, el puntero rápido alcanza al lento y se encuentran. También permiten encontrar dónde empieza un ciclo y dividir una lista por la mitad para la ordenación por mezcla o para comprobar si una lista se lee igual en ambas direcciones.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def middleNode(values, next):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Esperado
5