检查链表是否是回文 - 我在这里遗漏了什么？

Question

这是我对问题的尝试解决方案。

 public boolean isPalindrome(ListNode head) {

    if(head == null || head.next == null)

        return true;

    ListNode hare = head;

    ListNode tort = head;

    while(hare!=null && hare.next!=null) {

        //System.out.print("Hare "+ hare.val +"tort  "+tort.val);

        hare = hare.next.next;

        tort = tort.next;

    }

    //Tort is the middle of the list

    reverseLL(tort);

    ListNode tmp = tort;

    printList(tmp);

    while(tort!=null) {

        if(head.val!=tort.val)

            return false;

        head = head.next;

        tort = tort.next;

        continue;

    }

    return true;

}

private ListNode reverseLL(ListNode head) {

    if(head == null || head.next == null) {

        return head;

    }

    ListNode nextElem = head.next;

    //System.out.println("Processing "+head.val);

    head.next = null;

    ListNode rev = reverseLL(nextElem);

    nextElem.next = head;

    return rev;

}

 private void printList(ListNode head){

        while(head!=null){

            System.out.println("[" +head.val + "]");

            head = head.next;

        }

    }

但我注意到一些我无法弄清楚的非常奇怪的事情。tort当前结束于链表的中间。然而，从头到尾的逆转tort似乎将侵权行为与链表的其余部分断开。

例如，如果输入是 1->2->3->4，tort 最终是 3，但是在从 tort 反转它之后打印列表只打印 3，即。3 与列表的其余部分断开连接。

我已经reverseLL单独测试过它并且它可以工作，但是当它作为 isPalindrome 方法的一部分应用时。知道我可能缺少什么吗？

Answer 1

似乎您想检查回文就位，但您没有说明这样的要求，所以我提出了一种更直接的算法：初始化堆栈遍历列表并将每个元素压入栈顶直到栈不为空：弹出栈顶将弹出的元素与列表的头部进行比较如果不相等，返回&nbsp;false弹出另一个元素，在列表中向前移动一个元素返回&nbsp;true这是一个带有泛型的 Java 实现：&nbsp; public <T> boolean isPalindrome(ListNode<T> head) {&nbsp; &nbsp; &nbsp; &nbsp; Stack<ListNode<T>> stack = new Stack<>();&nbsp; &nbsp; &nbsp; &nbsp; ListNode<T> x = head;&nbsp; &nbsp; &nbsp; &nbsp; while(x != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; stack.push(x);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = x.next;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; while(!stack.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ListNode<T> el = stack.pop();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(el.t != head.t) return false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; head = head.next;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }该算法在时间上为 O(n)，在空间上为 O(n)。

Answer 2

在第一个 while 循环中找到链表的中间时，为什么不维护一个指向 tort 之前节点的指针：ListNode prev_tort = head;while(hare!=null && hare.next!=null) {&nbsp; &nbsp; //System.out.print("Hare "+ hare.val +"tort&nbsp; "+tort.val);&nbsp; &nbsp; hare = hare.next.next;&nbsp; &nbsp; prev_tort = tort;&nbsp; &nbsp; tort = tort.next;}现在，当元素数为偶数时，hare 将为 NULL。因此，对于奇数情况，跳过中间节点：if(hare != NULL){&nbsp; &nbsp; &nbsp;tort = tort.next;&nbsp; &nbsp; &nbsp;prev_tort = prev_tort.next;}tort = reverseLL(tort);prev_tort.next = tort;&nbsp; // only to ensure list is connected然后是您的比较代码。此外，在 reverseLL() 函数中：ListNode rev = reverseLL(nextElem);head.next.next = head;head.next = NULL;return rev;如果我理解正确，您正在尝试通过反转后半部分来检查列表是否为回文。在那种情况下，对于输入 1->2->3->4，在反转下半场后不应该 tort 指向 4 吗？这就是上面的代码所做的（列表将是：1->2->4->3）。