Palindrome Linked List
Recibes 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 marca 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 true si los valores se leen igual desde la cabeza hasta el final que desde el final hasta la cabeza, y false en caso contrario.
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
- Devuelveboolean
- true si la lista se lee igual en ambas direcciones
Restricciones
1 ≤ L ≤ 5000, dondeLes la longitud denexty devalues.-100 ≤ values[i] ≤ 100- Cada
next[i]es-1o un índice de nodo de0aL-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 = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- Salida
- true
- Explicación
- Los enlaces visitan los nodos
0, 4, 1, 3, 2, así que la lista es3, 1, 4, 1, 3. Los dos 3 coinciden, los dos 1 coinciden y el4del medio no tiene pareja con la que comprobarlo.
- Entrada
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- Salida
- true
- Explicación
- La lista visita los nodos
0, 2, 3, 1y lee4, 9, 9, 4, lo mismo en ambas direcciones.
- Entrada
- next = [2, -1, 1]values = [1, 2, 1]
- Salida
- false
- Explicación
- El arreglo
valueses[1, 2, 1], pero la lista visita los nodos0, 2, 1y lee1, 1, 2. Al revés, eso es2, 1, 1, así que la respuesta esfalse.
Para ir más allá
¿Puedes hacerlo en tiempo O(L) con memoria adicional O(1)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Una comprobación de palíndromo compara el primer valor con el último, el segundo con el penúltimo, y así sucesivamente. En una lista simplemente enlazada solo puedes avanzar. ¿Qué haría que el extremo posterior fuera accesible?
Copiar los valores en un array siguiendo el orden de la lista funciona, pero cuesta
O(L)de memoria. Sin la copia, hay que recorrer la segunda mitad hacia atrás. Cambiar sus enlaces puede hacerlo posible.Encuentra el punto medio con dos punteros:
fastavanza dos enlaces cada vez queslowavanza uno. Cuandofastya no puede avanzar,slowmarca el final de la primera mitad. Invierte los enlaces después deslow, luego recorre desde la cabeza y desde el antiguo último nodo al mismo tiempo y compara.
Solución
Una comprobación de palíndromo empareja cada valor con su reflejo del otro extremo. Una lista enlazada simple solo avanza, así que la parte difícil es leer la mitad final en orden inverso. Una copia en un arreglo lo hace usando O(L) de memoria, donde L es el número de nodos; invertir los enlaces de la segunda mitad lo hace usando O(1).
copia los valores en un arreglo
Intuición
Un puntero aquí es el índice de un nodo, y avanzar es node = next[node]. Recorre la lista una vez y copia cada valor en un arreglo, que puedes leer desde ambos extremos. Compara el primer y el último valor, mueve ambos índices hacia el centro y devuelve false si hay alguna discrepancia. Si la longitud es impar, el valor del medio es su propio compañero.
Hay que leer todos los valores, así que el tiempo O(L) es el mejor posible. El costo es de L enteros adicionales.
Algoritmo
- Recorre los nodos desde
0hasta-1y agrega cadavalues[node]a un arreglo. - Establece
i = 0yjen el último índice. - Mientras
i < j, devuelvefalsesi los dos valores son diferentes; de lo contrario, aumentaiy disminuyej. - Devuelve
true.
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return TrueInvierte la segunda mitad en el mismo lugar
Intuición
Invierte los enlaces de la segunda mitad en lugar de copiarla: así, un recorrido desde el antiguo último nodo conduce hacia el medio. Para encontrar el medio, avanza fast dos enlaces por cada enlace que avanza slow, mientras fast tenga dos enlaces por delante. slow se detiene en el último nodo de la primera mitad, el nodo del medio cuando L es impar. En el primer ejemplo, slow recorre 0 → 4 → 1, mientras fast recorre 0 → 1 → 2, así que slow se detiene en el 4.
Invierte los nodos que vienen después de slow; después, recorre la lista desde la cabeza con left y desde la mitad invertida con right a la vez: 3 con 3, después 1 con 1. La mitad invertida nunca es más larga que la primera mitad, así que detenerse cuando termina right compara exactamente los pares importantes. Cada fase recorre como máximo L nodos y almacena unos pocos enteros. En R, cambiar next_ copia el vector una vez, así que R usa memoria O(L).
Algoritmo
- Establece
slow = fast = 0. Mientras quenext[fast]ynext[next[fast]]no sean ambos-1, avanzaslowun enlace yfastdos. - Invierte la lista que comienza en
next[slow]: para cada nodo, guarda su enlace, haz que apunte aprevy luego avanzaprevy el nodo. - Establece
left = 0yright = prev, la cabeza de la mitad invertida. - Mientras
right != -1, devuelvefalsesi hay una discrepancia; de lo contrario, avanza ambos punteros un enlace. - Devuelve
true.
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
Errores comunes y casos límite
- Comprobar los arreglos en lugar de la lista. En el tercer ejemplo,
valueses[1, 2, 1], pero la lista muestra1, 1, 2. - Probar solo
next[fast] != -1.fastpuede saltar después a-1y leernext[-1], lo que está fuera de rango en la mayoría de los lenguajes y, sin avisar, accede a la última entrada en Python y Ruby. - Comparar hasta que termine
leften lugar deright. El nodo del medio sigue enlazado a la antigua segunda mitad, así que el recorrido desde la cabeza es el más largo. - Sobrescribir
next[node]durante la inversión antes de guardarlo, lo que hace que se pierda el resto de la lista. - En Lua y R, donde los arreglos empiezan en 1, leer
next[node]para un identificador de nodo basado en 0. Leenext[node + 1].
Preguntas frecuentes3
¿Cuál es la complejidad temporal de la comprobación de una lista enlazada palíndroma?
Cada enfoque es O(L) para una lista de L nodos, porque hay que comparar cada valor. Copiar los valores en un array o en una pila usa O(L) de memoria adicional; invertir la segunda mitad in situ usa O(1).
¿Cómo encuentran los punteros rápido y lento el centro de una lista enlazada?
Ambos comienzan en la cabeza, y el puntero rápido avanza dos pasos por cada paso del lento. Cuando el puntero rápido llega al final, ha recorrido toda la lista, y el lento, la mitad.
¿Invertir la mitad de la lista destruye la entrada?
Sí, cambia los enlaces de la segunda mitad y, en la mayoría de los lenguajes, ese arreglo es del propio llamador. Si todavía necesitas la lista, termina la comparación sin retornar antes de tiempo y luego vuelve a invertir esa mitad. El nodo del medio sigue enlazado al primer nodo de esa mitad, así que la lista vuelve a estar completa usando memoria adicional O(1).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def isPalindrome(next, values):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
Salida Esperada
true