反向链表:为什么head=head.next的位置很重要

Question

有人能解释为什么这条线head=head.next的位置必须在curr=head之后，而不是再往下吗？最初，我将head=head.next放在while循环的最后一行，但只得到最后一个节点。例如，如果输入是[1,2,3]，我将使用第二个代码块得到[1]，使用第一个代码块获得[3,2,1]。

正确：

def reverseListIterative(head: ListNode):
prev = None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev

错误：

def reverseListIterative(head: ListNode):
prev = None
while head:
curr = head
curr.next = prev
prev = curr
head = head.next
return prev

Answer 1

您可以通过跟踪代码流中每个变量的内容来了解这一点(您甚至不需要运行它(：

假设我们从列表1->2->3

prev  curr head  head.next  curr.next
----  ---- ----  ---------  --------- 
prev = None               None  -    1     2          -
while head:
curr = head           None  1    1     2          2  
curr.next = prev      None  1    1     None       None      *** 
prev = curr           1     1    1     None       None 
head = head.next      1     1    None  -          None    
return prev

当您将prev(None(分配给curr.ext时，您将失去与head.next的连接，因为head也指向节点#1。