Saltar al contenido

Una cadena que se lee igual al revés

Fácil#fast-slow-pointers#in-place-reversal~20 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

Restricciones

  • the list has between 1 and 10⁵ nodes
  • each node holds a digit

¿Lo que te frena es la idea y no el código? Punteros rápido y lento lo explica.

Python 3Ctrl+Enter ejecuta