Determinar si una lista enlazada es palíndroma

  
Introducción
       
En este artículo, aprenderás a Determinar si una lista enlazada es palíndroma. Este es un problema de programación básico sobre listas enlazadas.

En este artículo, cubriremos los siguientes temas:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

Una solución simple a este problema consiste en utilizar una pila auxiliar para guardar los elementos en el orden buscado.

                       

Problema
Desarrolle una función que determine si una lista enlazada es palíndroma.

            

Pasos para realizar el ejercicio:
1.-  Se crea una pila para almacenar los valores de la primera mitad de la lista vinculada. También se crean dos punteros aux y medio para recorrer la lista enlazada.
Tanto aux como medio se inicializan en aux. 
        
2.- Se recorre la lista enlazada mediante un bucle while. El bucle continúa mientras aux  y su siguiente posición no sean nulo.
    Dentro del bucle, el valor del puntero medio se apila.
    Luego, se avanza medio a su siguiente posición.
    aux avanza dos nodos a la vez. Esto se debe a que queremos omitir la segunda mitad de la lista por ahora, ya que en este paso solo nos interesa la primera mitad.
            
3.- Después de que sale el ciclo, si la longitud de la lista enlazada es impar, habrá un nodo adicional en el medio que no forma parte de la primera mitad. Se comprueba si aux no es nulo. Si es así, significa que la lista tiene un número impar de elementos y el puntero medio debe avanzar a su siguiente posición.
        
4.- Se recorre la pila mientras no esté vacía. Dentro del bucle, el tope superior de la pila se extrae y se almacena en una variable llamada tope. Luego, el código compara el valor de tope con el valor del nodo actual al que apunta medio.

5.- Si los valores no son iguales, significa que la lista enlazada no es un palíndromo y la función devuelve falso. Si los valores son iguales, se hace pop de la pila y el puntero medio avanza al siguiente nodo.
           
6.- Si sale del while, retorna true.

            

Código en Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> pila = new Stack<>();
        ListNode aux = head;
        ListNode medio = head;

        // Paso #2 (Step #2)
        while (aux != null && aux.next != null) {
            pila.push(medio.val);
            medio = medio.next;
            aux = aux.next.next;
        }

        // Paso #3 (Step #3)
        if (aux != null) medio = medio.next;

        // Paso #4 (Step #4)
        while (!pila.isEmpty()) {
            int tope = pila.pop();
            if (medio.val != tope) return false;
            medio = medio.next;
        }
        return true;

    }
}

Código en php

class Solution {
    function isPalindrome($head) {
        $pila = []; 
        $aux = $head;
        $medio = $head;

        // Paso#2
        while ($aux && $aux->next) {
            $pila[] = $medio->val; 
            $medio = $medio->next;
            $aux = $aux->next->next;
        }

        if ($aux) {
            $medio = $medio->next;
        }

        while (count($pila) > 0) {
            $tope = array_pop($pila); 
            if ($medio->val != $tope) {
                return false;
            }
            $medio = $medio->next;
        }

        return true;

    }
}

Código en Python

class Solution(object):
    def isPalindrome(self, head):
        pila = []  # Use a list as a stack in Python
        aux = head
        medio = head

        while aux and aux.next:
            pila.append(medio.val)
            medio = medio.next
            aux = aux.next.next

        if aux:
            medio = medio.next

        while pila:
            tope = pila.pop()
            if medio.val != tope:
                return False
            medio = medio.next

        return True

        

Código en C++

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //Paso#1
        stack<int> pila;
        ListNode *aux = head;
        ListNode *medio = head;

        //Paso#2
        while(aux && aux->next){
            pila.push(medio->val);
            medio = medio->next;
            aux = aux->next->next;
        }

        //Paso#3
        if(aux) medio = medio->next;

        //Paso#4
        while(!pila.empty()) {
            int tope = pila.top();
            if(medio->val!=tope) return false;

            pila.pop();
            medio = medio->next;
        }
		return true;
    }
};

Código en JavaScript

  var isPalindrome = function(head) {
    // Paso #1: Create a stack and pointers
    const stack = [];
    let aux = head;
    let medio = head;

    // Paso #2: Push values to stack and find middle node
    while (aux && aux.next) {
      stack.push(medio.val);
      medio = medio.next;
      aux = aux.next.next;
    }

    // Paso #3: Handle odd-length lists
    if (aux) medio = medio.next;

    // Paso #4: Compare values from stack and linked list
    while (stack.length > 0) {
      const tope = stack.pop();
      if (medio.val !== tope) return false;
      medio = medio.next;
    }

    return true;
};

        
    
Conclusión
En este artículo, aprendiste a Determinar si una lista enlazada es palíndroma. Este es un problema de programación básico sobre listas enlazadas.

La solución presentada en este artículo utiliza una pila para guardar el orden.