Java奇怪的NullPointerException在反转链接列表时
我正在研究一个名为“回文链表”的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类是预定义的,所以我不需要自己编写
# 1 楼答案
也许,您应该使用Java公共集合中的
iterator
和descendingIterator
来实现isPalindrome
方法:更新:使用反向列表为请求的单链表提供解决方案:
# 2 楼答案
您给定的输入为1->;2->;所以你的n是3
在进入while循环之前,您已经初始化了
你的程序进入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为空
电流=温度;当温度=零时,电流为零
第四次迭代