反向链表：为什么 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.next 时，您会失去来自 head.next 的连接，因为 head 也指向节点 #1。