Java奇怪的NullPointerException在反转链接列表时

Question

我正在研究一个名为“回文链表”的LeetCode问题，在给出一个单链表的情况下，确定它是否是回文。例如，如果输入为1->；2->；2->；1.它应该输出true

我通过使用额外的空间（将列表转换为ArrayList）解决了这个问题，现在我尝试用另一种方法来解决它，反转列表的第二部分，然后比较这两部分。虽然我可能没有以最好的方式实现这个想法，但我希望代码要么工作，要么输出错误的答案（然后我可以改进代码）。然而，一个奇怪的NullPointerException发生了，我不知道为什么

我的代码如下所示，用于测试的输入列表为1->；2->；3。我还添加了一些打印以帮助调试

// reverse the 2nd half of list and then compare the two halves

class Solution {
    public boolean isPalindrome(ListNode head) {
        int n = 0; // list length
        ListNode p = head;
        while (p != null) { // obtain list length n 
            n++;
            p = p.next;
        }
        p = head;


        int m = 0;
        ListNode prev = null, curr = null, temp = null;
        while (p != null) { // reverse the 2nd half of list
            m++;
            if (m == n/2 + 1) {
                prev = p;
                curr = p.next;
                p = p.next;

                System.out.println(curr.val);
                System.out.println(curr);
                //System.out.println(p);
            }
            else if (m > n/2 + 1) {
                //System.out.println(p);
                System.out.println(curr);
                //System.out.println(curr.val);

                temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
                p = p.next;
            }
            else 
                p = p.next;
        }


        int k = 1;
        while (k < n/2 + 1) { // compare the two halves, prev points at the last node
            if (head.val != prev.val)
                return false;
            head = head.next;
            prev = prev.next;
            k++;
        }
        return true;
    }    
}

输出（当输入1->；2->；3，再加上一些打印语句时）是：

NullPointerException thrown at the line: temp = curr.next; (which is inside the else if)

the code also prints:
3
ListNode@77a567e1
ListNode@77a567e1
null 

curr指的是最后一个节点，所以curr。瓦尔3岁。我不明白的是为什么两个系统。出来println（curr）给出不同的输出。curr不应该指最后一个节点吗？输出中的null来自哪里？我认为这就是为什么会发生NullPointerException的关键

我现在很困惑，如果有人能帮我理解出了什么问题，我将非常感激！谢谢

编辑：因为这是一个LeetCode问题，ListNode类是预定义的，所以我不需要自己编写

Answer 1

也许，您应该使用Java公共集合中的iterator和descendingIterator来实现isPalindrome方法：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
System.out.printf("list: %s palindrome: %s%n", list,  isPalindrome(list));
// ...

  public boolean isPalindrome(LinkedList<Integer> list) {
    Iterator<Integer> directIterator = list.iterator();
    Iterator<Integer> reverseIterator = list.descendingIterator();
    int count = list.size() / 2;
    while (directIterator.hasNext() && reverseIterator.hasNext() && count  > 0) {
      if (directIterator.next().intValue() != reverseIterator.next().intValue()) {
        return false;
      }
    }
    return true;
  }

更新：使用反向列表为请求的单链表提供解决方案：

    public boolean isPalindrome(ListNode head) {
        // empty and single element list is palindrome
        if (null == head || null == head.next) {
            return true;
        }
        // build reverse linked list
        ListNode curr = head;
        ListNode tail = new ListNode(curr.val);
        tail.next = null;
        ListNode prev = null;
        int size = 1;
        while (null != curr.next) {
            prev = tail;
            curr = curr.next;
            tail = new ListNode(curr.val);
            tail.next = prev;
            size++;
        }
        // move both from head and from tail to the middle element
        int half = size / 2;
        curr = head;
        prev = tail;
        while (null != curr && null != prev && half  > 0) {
            if (curr.val != prev.val) {
                return false;
            }
            curr = curr.next;
            prev = prev.next;
        }
        return true;
    }

Answer 2

您给定的输入为1->；2->；所以你的n是3

在进入while循环之前，您已经初始化了

curr = null;

你的程序进入while循环

第一次迭代

• m++；m=1的值

• 1==3/2+1 false，因此输入else，如果再次为false，则转到else

第一次迭代后的值

m=1；curr=null prev=null和p=2（指向节点值2）

第二次迭代

• m=2

• 如果

• 上一个=1，当前&；p=3（值为3的节点）

• 印钞。val为3，curr为打印“ListNode@77a567e1“

第二次迭代后的值

m=2；上一个=2，当前&；p=3（值为3的节点）

第三次迭代

• m=3

• 3>；3/2+1为真，因此如果

• “打印当前打印”ListNode@77a567e1“

• 温度=电流。next当curr为3时，next为空

• 电流=温度；当温度=零时，电流为零

第四次迭代

so as curr is null on forth iteration it prints null and throws null pointer exception.