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

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

似乎您想检查回文就位，但您没有说明这样的要求，所以我提出了一种更直接的算法：

1. 初始化堆栈

2. 遍历列表并将每个元素压入栈顶

3. 直到栈不为空：

1. 弹出栈顶

2. 将弹出的元素与列表的头部进行比较

3. 如果不相等，返回 false

4. 弹出另一个元素，在列表中向前移动一个元素

4. 返回 true

这是一个带有泛型的 Java 实现：

  public <T> boolean isPalindrome(ListNode<T> head) {

        Stack<ListNode<T>> stack = new Stack<>();

        ListNode<T> x = head;

        while(x != null) {

            stack.push(x);

            x = x.next;

        }

        while(!stack.isEmpty()) {

            ListNode<T> el = stack.pop();

            if(el.t != head.t) return false;

            head = head.next;

        }

        return true;

    }

该算法在时间上为 O(n)，在空间上为 O(n)。

Answer 2

在第一个 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）。