O prolbema de verificar se uma lista encadeada é um palíndromo (ou seja, se seus elementos leem o mesmo para frente e para trás) é um desafio clássico em estruturas de dados. Este artigo explora duas abordagens distintas para resolver este problema, ambas utilizando a técnica de inversão de listas, mas com diferentes estratégias para o ponto de comparação.

Para todas as soluções, consideraremos a seguinte definição de nó de lista encadeada:

/**
 * Definição para um nó de lista encadeada simples.
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Abordagem 1: Inversão Completa da Lista

Esta solução propõe a criação de uma cópia da lista original, mas com seus nós em ordem inversa. Após a criação da lista invertida, basta percorrer a lista original e a lista invertida simultaneamente, comparando os valores de seus nós. Se em algum momento os valores não coincidirem, a lista não é um palíndromo. Se ambas as listas forem percorridas até o fim sem discrepâncias, então a lista original é um palíndromo.

Esta estratégia é conceitualmente simples, mas requer espaço adicional proporcional ao número de nós na lista (O(N)) para armazenar a cópia invertida.

Implementação (Inversão Completa)

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // Uma lista vazia ou com um único nó é um palíndromo
        }

        ListNode originalCurrent = head;
        ListNode reversedCopyHead = createReversedCopy(head); // Cria uma cópia completa invertida

        while (originalCurrent != null) { // Itera através de ambas as listas
            if (originalCurrent.val != reversedCopyHead.val) {
                return false; // Valores não coincidem, não é um palíndromo
            }
            originalCurrent = originalCurrent.next;
            reversedCopyHead = reversedCopyHead.next;
        }
        return true; // Todas as comparações foram bem-sucedidas
    }

    /**
     * Helper que cria e retorna uma NOVA lista encadeada com os nós da lista original em ordem inversa.
     *
     * @param originalNode O nó inicial da lista a ser invertida.
     * @return O nó inicial da nova lista invertida.
     */
    private ListNode createReversedCopy(ListNode originalNode) {
        ListNode reversedHead = null; // A cabeça da nova lista invertida
        ListNode current = originalNode;

        while (current != null) {
            // Cria um novo nó com o valor atual e o liga à parte já invertida
            reversedHead = new ListNode(current.val, reversedHead);
            current = current.next;
        }
        return reversedHead;
    }
}

Abordagem 2: Ponteiros Rápido/Lento e Inversão da Segunda Metade

Esta abordagem otimizada busca resolver o problema com uma complexidade de espaço menor (O(1) se a inversão for feita in-place e a lista for restaurada, ou O(N) se a inversão criar novos nós, como na Abordagem 1). Ela envolve três etapas principais:

1. Encontrar o Meio da Lista: Utiliza ponteiros "rápido" e "lento". O ponteiro rápido avança dois nós por vez, enquanot o lento avança um nó por vez. Quando o ponteiro rápido atinge o final da lista, o ponteiro lanto estará no meio.
2. Inverter a Segunda Metade: A partir do ponto médio encontrado, a segunda metade da lista é invertida.
3. Comparar: A primeira metade da lista original é comparada com a segunda metade invertida. Se todos os valores corresponderem, a lista é um palíndromo.

Para listas de comprimento ímpar, o nó do meio é ignorado durante a comparação, pois ele não afeta a propriedade de palíndromo.

Implementação (Ponteiros Rápido/Lento e Inversão da Segunda Metade)

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // Uma lista vazia ou com um único nó é um palíndromo
        }

        ListNode slowWalker = head; // Ponteiro lento
        ListNode fastWalker = head; // Ponteiro rápido
        ListNode firstHalfEnd = head; // Rastreia o final da primeira metade

        // 1. Encontrar o início da segunda metade
        while (fastWalker != null && fastWalker.next != null) {
            firstHalfEnd = slowWalker; // 'firstHalfEnd' será o nó ANTES de 'slowWalker'
            slowWalker = slowWalker.next;
            fastWalker = fastWalker.next.next;
        }

        // Neste ponto:
        // - 'slowWalker' aponta para o início da segunda metade (ou o nó do meio para listas de comprimento ímpar).
        // - 'fastWalker' é null (comprimento par) ou o último nó (comprimento ímpar).

        ListNode secondHalfStart = slowWalker;
        if (fastWalker != null) { // Lista de comprimento ímpar, 'slowWalker' é o nó do meio
            secondHalfStart = slowWalker.next; // Pula o nó do meio para iniciar a segunda metade
        }

        // 2. Inverter a segunda metade (cria uma nova lista invertida)
        ListNode reversedSecondHalf = createReversedCopy(secondHalfStart);

        // 3. Comparar a primeira metade (a partir de 'head') com a segunda metade invertida
        ListNode p1 = head; // Ponteiro para a primeira metade
        ListNode p2 = reversedSecondHalf; // Ponteiro para a segunda metade invertida

        while (p2 != null) { // Compara até o final da segunda metade invertida
            if (p1.val != p2.val) {
                return false; // Valores não coincidem, não é um palíndromo
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true; // Todas as comparações foram bem-sucedidas
    }

    /**
     * Helper que cria e retorna uma NOVA lista encadeada com os nós da lista original em ordem inversa.
     *
     * @param originalNode O nó inicial da lista a ser invertida.
     * @return O nó inicial da nova lista invertida.
     */
    private ListNode createReversedCopy(ListNode originalNode) {
        ListNode reversedHead = null; // A cabeça da nova lista invertida
        ListNode current = originalNode;

        while (current != null) {
            // Cria um novo nó com o valor atual e o liga à parte já invertida
            reversedHead = new ListNode(current.val, reversedHead);
            current = current.next;
        }
        return reversedHead;
    }
}