saber - palindromo en java recursividad

¿Cómo verificar si una lista vinculada es un palíndromo o no en Java?

Question

Escribí un código para verificar si una lista vinculada individualmente es un palíndromo. E hice dos pasos:

1º. revertir la lista enlazada original.

2do. Verifique si la lista enlazada original e invertida tiene el mismo elemento.

    public static Boolean isPalindrome(Node input){
        Node reversed= reverse(input);
        while (input!=null){
            if(input.item!=reversed.item)
                return false;
            input=input.next;
            reversed=reversed.next;
            }
            return true;
    }
    static Node head;
    public static Node reverse(Node input){
        if(input==null || input.next==null){
            head=input;
            return input;
        }
        else{
            reverse(input.next);
            input.next.next=input;
            input.next=null;
            return head;
        }
    }

Este programa funciona Pero pensé que, cuando ejecutara el método inverso, dado que la cabeza de la lista vinculada original pasaría, entonces la lista vinculada original también podría cambiar, por lo que isPalindrome también debería ser verdadera, ¿no? ¿Tengo razón o puedes decirme si malinterpreté algún concepto? Gracias

Esta es la función principal y cómo uso ese código:

public static void main(String [] args){
    Node a=new Node(9);
    Node b=new Node(8);
    Node c=new Node(7);
    Node d=new Node(6);
    a.next=b;
    b.next=c;
    c.next=d;
    //d.next=c;
    Boolean tf=isPalindrome(a);
    if (tf)
        System.out.println("Is Palindrome!");
    else
        System.out.println("Not Palindrome");
}

Answer 1

En realidad, tu método no está funcionando. Pruébalo por una lista que contiene 3,4,5,3 . Volverá true .

Además, cambia la lista que se le pasó, lo cual no es una muy buena idea. Si hace algo como System.out.println(a) (suponiendo que haya escrito un método toString() adecuado) después de ejecutar su método, se sorprenderá al descubrir que solo tiene un elemento ...

Esto es así porque pasar una referencia a un objeto es como pasar un puntero en idiomas como C Si cambia el contenido de ese objeto (y en última instancia lo hace, porque a la reverse pone null en su next ), entonces permanece modificado.

Entonces, ¿por qué su programa es true ? Porque la input , como dije, se convierte en una lista de un solo elemento. reversed contiene la lista completa invertida, y la input simplemente apunta a su último elemento. Como haces un bucle en la input , si el primero y el último elemento son iguales , obtendrás la true , ya sea que la lista sea o no palíndrica. Esto se debe a que solo itera en el elemento al que apunta la input .