Python递归反转链表报局部变量赋值前引用错误求优化方案

第一版代码触发local variable "new_head" referenced before assignment是Python作用域规则导致的：如果在嵌套函数recur内部对某个变量名做赋值操作，Python会默认将该变量判定为recur的局部变量，不会向外层函数作用域查找。执行curr_head.next = new_head时，局部作用域内的new_head还未完成赋值，就会抛出引用前未定义的错误。

你写的第二版数组包裹写法能运行，是因为列表是可变对象，嵌套函数内只修改列表内部存储的元素，没有对arr变量名本身做重新赋值，Python会正确向外层查找arr对象，不会将其识别为局部变量，但这种写法确实不够直观简洁。

方案1：用nonlocal关键字（最小改动修正原有写法） #

Python3提供的nonlocal关键字专门用于声明嵌套函数内的变量引用自外层非全局作用域，不需要额外用数组包裹变量，只需要在嵌套函数内加一行声明即可：

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    
    new_head = None
    
    def recur(curr_head):
        nonlocal new_head  # 声明new_head引用自外层函数作用域
        if curr_head is None:
            return
        
        next_node = curr_head.next
        curr_head.next = new_head
        new_head = curr_head
        recur(next_node)
        
    recur(head)
    return new_head

编码规范提示：Python中判断对象是否为None时，用is None比== None执行效率更高、写法更标准。

方案2：带返回值的递归写法（无外部变量的标准递归实现） #

不需要维护外部变量、不需要嵌套函数，直接通过递归返回值传递反转后的链表头节点，逻辑更内聚：

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 递归终止条件：空节点或单节点本身就是反转后的头
    if head is None or head.next is None:
        return head
    # 递归反转当前节点之后的子链表，拿到反转后的新头节点
    new_head = self.reverseList(head.next)
    # 将当前节点接到反转后子链表的尾部
    head.next.next = head
    # 断开当前节点原有指向，避免形成链表环
    head.next = None
    return new_head

方案3：迭代写法（工程首选，空间复杂度O(1)） #

没有递归栈的额外开销，仅用两个指针遍历一次链表即可完成反转，性能最优：

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head
    while curr is not None:
        next_temp = curr.next  # 暂存下一个节点，避免断链后丢失遍历位置
        curr.next = prev       # 反转当前节点的指向
        prev = curr            # 前驱指针前移
        curr = next_temp       # 当前遍历指针前移
    return prev

内容的提问来源于stack exchange，提问作者Michael Xia