检查链表是否是回文

Question

public boolean palindromLinkedList() {
    //find size
    Node temp = head;
    int size=0;
    while(temp != null){
        size++;
        temp=temp.next;
    }
    //find while loop iteration
    int c;
    if(size%2 ==0){
        c = size/2;
    }else{
        c = (size+1)/2;
    }
    //intialise start and end pointer
    Node start = head;
    Node end = tail;
    //index pointer
    int k =size-1;
    //loop for the palindrome condition
    while(c > 0)`
        if(start.data != end.data){
            return false;
        }
        start = start.next;
        Node find = head;
        k--;
        for(int i=0;i<=k;i++){
            find = find.next;
        }
        end = find;
        c--;
    }
    return true;
}

我尝试使用类似于两个指针的方法来检查链表是否是回文。
我初始化了两个变量：

start = head

和

end = tail

。

start从start开始检查节点，end从tail开始检查，检查start和end的数据是否相等后，我将更改后的start指向下一个节点，并使用for循环找到end的前一个节点，这个过程继续，直到指针到达中间节点。

如果链表是回文，则返回 true，否则返回 false。我认为我的方法是正确的，但我似乎错过了一些东西。

Answer 1

看来你实现了自己的链表，使得这个问题很难回答。

但是，假设您的代码类似于 java.util.LinkedList：

java中的

==

检查引用，而不是给定的对象。您应该使用

.equals

来比较节点数据。 更好的是

Objects.equals(start.data, end.data)

，因为它还可以处理

null

。

这种行为的一个很好的例子是字符串。 Java 收集您在程序中硬编码的字符串，因此它有时可以工作，但大多数时候却不能。

"abc" == "abc" // true
"abc".equals("abc") // true
"abc" == new String("abc") // false
"abc".equals(new String("abc")) // true
"abc" == getUserPassword() // false
"abc".equals(getUserPassword()) // true if user enters abc

我建议您实现双链表，因为它将提高性能，并在这种情况下使您的生活变得更加轻松。 它基本上也添加了对前一个节点的引用。 因此，您不需要循环遍历所有元素，但可以使用

end.previous

获取前一个节点。

Answer 2

问题出在这行代码：

        for (int i = 0; i <= k; i++) {

此循环进行一次迭代到多次迭代。更改为：

        for (int i = 0; i < k; i++) {

这将解决即使是最简单的测试用例也会得到的错误输出。

但是现在你会遇到另一个问题：这段代码太慢了。您必须重复循环才能确定

end

之前的节点成本太高，并且使您的实现具有 O(𝑛²) 时间复杂度。您需要想出更好的主意。

这个问题之前已经被解决过多次，并且在这个网站上您还可以找到更有效的方法来完成它的解释。