如何在Java中检查链表是否是回文？ [英] How to check if a linked list is a palindrome or not in Java?

问题描述

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

I wrote a code to check if a singly linked list is a palindrome. And I made two steps:

1st。反转原始链表。

1st. reverse the original linked list.

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

2nd. Check if the original and reversed linked list have the same element.

    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也应该返回true，对吧？我是对的还是你可以告诉我，如果我误解了任何概念？谢谢

This program works. But I thought, when execute the reverse method, since the original linked list's head gets passed in, so the original linked list might changed as well, so the isPalindrome should also return true, right ? Am I right or can you tell me if I misunderstood any concept? thanks

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

This is the main function and how I use that code:

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

推荐答案

实际上，你的方法是<他们不工作。尝试使用包含 3,4,5,3 的列表。它将返回 true 。

Actually, your method is not working. Try it for a list that contains 3,4,5,3. It will return true.

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

Also, it changes the list that was passed to it, which is not a very good idea. If you do something like System.out.println(a) (assuming you wrote a proper toString() method) after you run your method, you'll be surprised to find that it only has one item...

这的确是因为传递一个对象引用就像传递一个指针在 C 等语言中。如果你改变了那个对象的内容（最终你做了，因为在反向中你将 null 放在其 next ），然后它保持不变。

This is indeed because passing an object reference is like passing a pointer in languages like C. If you change the content of that object (and ultimately you do, because in reverse you put null in its next), then it stays changed.

那么为什么你的程序返回 true ？因为输入，正如我所说，成为一个单项目列表。 reverse 包含完整的反转列表，输入仅指向其最后一项。由于您循环输入，然后如果第一个和最后一个项目相同，您将获得 true - 无论清单是否为回文。那是因为你只迭代输入指向的一个项目。

So why does your program return true? Because input, as I said, becomes a one-item list. reversed contains the full reversed list, and input merely points to its last item. Since you loop on input, then if the first and last items are the same, you'll get true - whether or not the list is a palindrome. That's because you only iterate on the one item that input is pointing to.

这篇关于如何在Java中检查链表是否是回文？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！