如何检查链接列表是回文还是不是Java？

Question

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

1st。反转原始链接列表。

2nd。检查原始链接列表和反向链接列表是否具有相同的元素。

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

该程序的工作原理。但我认为，当执行反向方法时，由于原始链表的头部被传入，所以原始链表也可能发生改变，所以isPalindrome也应该返回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的列表。它将返回true。

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

这的确是因为传递一个对象引用像传递一个像C这样的语言的指针。如果您更改了该对象的内容（并且最终确实如此，因为在reverse中，您将null放在其next中），则它保持更改状态。

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