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

Question

我正在研究一个名为“回文链表”的LeetCode问题，其中给出了一个单链表，确定它是否是回文。例如，如果输入为1-

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

我的代码如下所示，测试的输入列表是1-

// 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时）-

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不应该指最后一个节点吗？输出中的空值来自哪里？我认为这就是为什么会发生NullPointerException的关键。

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

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

Answer 1

也许，您应该使用Java公共集合中的iterator和downingiterator使用LinkedList实现您的isAlindrome方法：

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-

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

curr=null；

你的程序在循环时进入

第一次迭代

>

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

第一次迭代后的值

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

第二次迭代

>

2==3/2如果

上一个=1，当前

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

第二次迭代后的值

m=2；上一个=2，当前

第三次迭代

>

m=3

3个

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

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

curr=temp； as temp=null curr is null

第四次迭代

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