Java如何判断链表是否为回文？

Question

我写了一个代码来检查单向链表是否是回文。我做了两个步骤：

第一。反转原始链表。

第二。检查原链表和反向链表是否有相同的元素

    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;
        }
    }

这个程序有效。但是我想，在执行reverse方法的时候，由于传入了原链表的头，所以原链表可能也会发生变化，所以isPalindrome也应该return true，对吧？我是对的还是你能告诉我我是否误解了任何概念？谢谢

这是主要功能以及我如何使用该代码：

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

实际上，您的方法不有效。尝试使用包含 3,4,5,3 的列表。它将 return true.

此外，它更改了传递给它的列表，这不是一个好主意。如果你在运行你的方法之后做类似 System.out.println(a) 的事情（假设你写了一个正确的 toString() 方法），你会惊讶地发现它只有一个项目......

这确实是因为传递对象引用就像在 C 等语言中传递指针一样。如果您更改该对象的内容（最终您会这样做，因为在 reverse 中您将 null 放入其 next），那么它会保持更改状态。

那么为什么你的程序 return true？因为 input，正如我所说，成为一个单项列表。 reversed 包含完整的反向列表，而 input 仅指向其最后一项。由于您在 input 上循环，然后 如果第一项和最后一项相同 ，您将得到 true - 无论列表是否为回文。那是因为您只迭代 input 指向的一项。

Java如何判断链表是否为回文？

How to check if a linked list is a palindrome or not in Java?

java

reference

linked-list

parameter-passing