Irving Juárez
Estaba pensando que el "reversar" los nodos de la segunda mitad puede llegar a ser complejo. Una solución que yo creo pudiera ser un poco más sencillas es la siguiente:
- Utilizar los dos apuntadores (rápido y lento) hasta llegar a la mitad de la lista enlazada
- Por cada nuevo nodo del apuntador lento, se estaría llenando un array, donde cada nuevo elemento se inserta al inicio de este array. En el caso del ejemplo, el array empieza como [1] y a la segunda iteración [9,1]
- Una vez que se haya llegado a la mitad, el apuntador rápido comienza a actuar de la misma manera que el lento (avanzando un nodo a la vez) y el lento deja de avanzar.
- El apuntador rápido (que ya esta actuando como el lento) compara su nuevo valor con el del array creado por el del apuntador lento. De esta manera cuando algún valor no coincida, sabremos que no es un palindromo.
. Creo que esta podría ser una solución más sencilla, aunque claramente sería más costosa en términos de Complejidad Espacial, ya que la solución que yo propongo tendría:
- Complejidad espacial de O(n)
- Complejidad temporal de O(n)
. Mientras que la solución propuesta en la clase tendría
- Complejidad espacial de O(1)
- Complejidad temporal de O(n)
. De cualquier forma creo que es un tradeoff que vale la pena tomar
