java - 检查链表是否是回文-我在这里缺少什么？

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 到最后的逆转似乎将 tort 与链表的其余部分断开。

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

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

Answer 1

在第一个 while 循环中找到链表的中间时，为什么不维护一个指向 tort 之前节点的指针:

ListNode prev_tort = head;
while(hare!=null && hare.next!=null) {
    //System.out.print("Hare "+ hare.val +"tort  "+tort.val);
    hare = hare.next.next;
    prev_tort = tort;
    tort = tort.next;
}

现在，当有偶数个元素时，hare 将为 NULL。所以，对于奇怪的情况，跳过中间节点:

if(hare != NULL){
     tort = tort.next;
     prev_tort = prev_tort.next;
}
tort = reverseLL(tort);
prev_tort.next = tort;  // 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)。