这是我的第一个问题。这可能是一个愚蠢的问题,但我在理解为什么以这种方式反转链表时顺序特别重要方面遇到了问题。 所以在这里我正在反转一个链表,它有效
ListNode prev = null, curr = head, next = head;
while (curr != null){
next = next.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
这工作得很好。 但是为什么我不能执行以下操作?
//edge cases:
if (head == null || head.next == null){
return head;
}
ListNode prev = null, curr = head, next = head.next; //change here
while (curr != null){
//line was previously here
curr.next = prev;
prev = curr;
curr = next;
next = next.next; //moved here
}
head = prev;
return head;
为什么我在 while 循环的开头而不是结尾设置 next = next.next 很重要?为什么我不能先设置 next = head.next,然后在循环结束时迭代它而不会得到空指针异常?
仅作为记录,您可以将反向操作视为从输入列表中弹出并推送到结果。不太史诗般的代码结果:
ListNode reverse(ListNode head) {
ListNode result = null;
while (head != null) {
ListNode elt = head; // pop into elt
head = head.next;
elt.next = result; // push elt onto result
result = elt;
}
return result;
}
进行此类更改时,将更改验证循环条件的状态。这导致了问题。
在工作代码中,我们有这个循环不变:
curr
和next
是平等的。它们要么都是null
的,要么都引用同一个节点。
在非工作代码中,这是不正确的,因为现在next
领先一步。相应的循环不变量现在next == curr.next
。所以当curr
是尾节点时,next
就会null
。在循环的下一次迭代中,执行next = next.next
,这是无效的,因为next
被null
,所以这引发了一个异常。
如果您将该声明作为条件,它将起作用:
if (next != null) next = next.next;
或者这也行得通:
if (next == null) break;
next = next.next;
但是这两种选择都不像原始代码那样优雅,因为现在每次迭代都要进行两次检查(循环条件和这个额外的检查)。事实上,这种额外的检查只是循环条件的重复,因为当时next
和curr
是相等的。