判断LinkedList是否为文物

Question

class ListNode {
    int data;
    ListNode next;
    ListNode(int data) { this.data = data; }
}

public static Boolean isListPalindrome(ListNode head) {

    if(head == null || head.next == null) {
        return true;
    } 

    ListNode n = head;
    ListNode fastPointer = head;
    ListNode reverse = reverseList(head);

    while(fastPointer.next != null || fastPointer != null) {
        if(n.data != reverse.data) {
            return false;
        }

        fastPointer = fastPointer.next.next;
        reverse = reverse.next;
        n = n.next;
    }

    return true;

}

public static ListNode reverseList(ListNode input) {

    ListNode current = input;
    ListNode next = input;
    ListNode prev = null;

    while(current != null) {

        next = current.next;
        current.next = prev;
        prev = current;
        current = next;

    }

    return prev;

}

----在反转列表之前-

// ListNode n：1-> 2-> 3-> 4-> 5

----反转列表后-

// ListNode n：1

// ListNode反向：5-> 4-> 3-> 2-> 1

基本上，我在这里所做的是反向链接，然后将原始列表与反向列表进行比较。但是，当我比较时，编译器返回“ NullPointerException”。

所以我将代码复制到IntelliJ中，并尝试打印原始列表和反向列表。原来原始列表中只有1个元素，另一方面，反向列表包含5个元素，原始列表也应该包含5个元素。

我该如何解决这个问题？

Answer 1

由于下一行，因为您在每次迭代中跳了两个步骤，所以出现了问题。当循环到达最后一个节点时，fastPointer变为null，因此您在NullPointerException的fastPointer.next != null检查中得到了while(fastPointer.next != null || fastPointer != null)。

fastPointer = fastPointer.next.next;

实际上，您在这里不需要fastPointer。

您可以简单地按照以下步骤操作：

public static Boolean isListPalindrome(ListNode head) {

    if(head == null || head.next == null) {
        return true;
    } 

    ListNode n = head;
    ListNode fastPointer = head;
    ListNode reverse = reverseList(head);

    while(n.next != null && reverse.next != null) {
        if(n.data != reverse.data) {
            return false;
        }
        reverse = reverse.next;
        n = n.next;
    }

    return true;
}