Una cadena que se lee igual al revés
La misión
Problema
Dada la cabeza de una lista simplemente enlazada de dígitos, devuelve True si los valores se leen igual de adelante hacia atrás que de atrás hacia adelante. La lista tiene entre 1 y 100 000 nodos. Apunta a O(n) de tiempo y O(1) de memoria extra, lo que descarta copiar los valores a una lista de Python, y deja la lista con su forma original cuando termines.
Ejemplos
Input: 1 -> 2 -> 2 -> 1
Output: True
Input: 1 -> 2
Output: False
Input: 7
Output: True
Por qué: caso límite: un solo nodo es un palíndromo
Pistas
0 / 3
Comparar el primer valor con el último es fácil en un array (arreglo), pero una lista simplemente enlazada no puede recorrerse hacia atrás. ¿Y si la mitad de atrás apuntara en el otro sentido?
Mueve un puntero lento un paso y uno rápido dos pasos a la vez. Cuando el rápido se queda sin nodos, el lento está al inicio de la mitad de atrás.
Invierte in-place la mitad de atrás, recórrela junto con la mitad del frente comparando valores y luego vuelve a invertirla para restaurar la lista.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- the list has between 1 and 10⁵ nodes
- each node holds a digit
Solución
Comprobar un palíndromo compara el i-ésimo valor desde el frente con el i-ésimo valor desde el final, y el único obstáculo es que el final de una lista simplemente enlazada no se puede recorrer al revés. Los punteros rápido y lento (fast and slow pointers) encuentran el medio en una pasada: cuando el rápido se queda sin nodos, el lento está en el primer nodo de la mitad de atrás (el propio nodo del medio, si la longitud es impar). Invertir la lista desde ahí hace que la mitad de atrás se pueda leer desde el último nodo hacia adentro, así que dos punteros pueden compararla con la mitad del frente. La comparación se detiene cuando se agota la mitad invertida, lo que además ignora un nodo del medio suelto. Invertir esa mitad una segunda vez vuelve a poner cada enlace en su lugar. El tiempo es O(n) y el espacio extra es O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def reverse(node):
prev = None
while node:
node.next, prev, node = prev, node, node.next
return prev
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # slow ends at the back half
slow, fast = slow.next, fast.next.next
tail = reverse(slow)
left, right, same = head, tail, True
while right:
if left.val != right.val:
same = False
break
left, right = left.next, right.next
reverse(tail) # restore the original links
return same
print(is_palindrome(build([1, 2, 2, 1]))) # -> True
print(is_palindrome(build([1, 2]))) # -> False
print(is_palindrome(build([7]))) # -> True
chain = build([1, 2, 3, 2, 1])
print(is_palindrome(chain), dump(chain)) # -> True [1, 2, 3, 2, 1]¿Lo que te frena es la idea y no el código? Punteros rápido y lento lo explica.