如何用Python递归法反转单链表？LeetCode206问题解惑

递归反转链表的核心是从链表尾部开始反向调整指针，利用递归的栈特性，先深入到链表的最后一个节点（它就是反转后的头节点），再回溯时逐个修改每个节点的next指针指向自己的前一个节点。下面结合输入[1,2,3]（对应链表1→2→3→None），一步步拆解你贴的代码逻辑：

代码逐步骤执行过程 #

原代码：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None
        print(newHead)
        return newHead

1. 递归深入阶段 #

• 第一次调用reverseList(1)：
  • head不为空，newHead初始化为1
  • head.next存在（指向2），触发递归调用reverseList(2)
• 第二次调用reverseList(2)：
  • head不为空，newHead初始化为2
  • head.next存在（指向3），触发递归调用reverseList(3)
• 第三次调用reverseList(3)：
  • head不为空，newHead初始化为3
  • head.next是None，跳过递归调用
  • 执行head.next = None（3的next本来就是None，无变化）
  • 打印3，返回3作为newHead（这就是反转后的链表头节点）

2. 回溯调整指针阶段 #

现在开始从最底层的递归栈回溯：

• 回到第二次调用reverseList(2)：
  • newHead被赋值为刚才返回的3
  • 执行head.next.next = head：这里head是2，head.next是3，所以把3的next指向2（此时链表变为3→2→None）
  • 执行head.next = None：把2的next设为None（避免后续形成环）
  • 打印3，返回3
• 回到第一次调用reverseList(1)：
  • newHead被赋值为返回的3
  • 执行head.next.next = head：head是1，head.next是2，把2的next指向1（此时链表变为3→2→1→None）
  • 执行head.next = None：把1的next设为None（最终完成反转）
  • 打印3，返回3作为最终结果

关键疑问解答 #

• 为什么递归调用reverseList(head.next)能返回正确的newHead？
  因为每次递归到最底层时，返回的是原链表的最后一个节点（也就是反转后的头节点），这个节点会在每一层回溯中被原样传递回来，所以最终返回的就是反转后的链表头。
• head.next.next = head的作用：
  把当前节点的下一个节点的next指针指向自己，完成局部的反转（比如把2→3改成3→2）。
• head.next = None的作用：
  避免链表出现环，比如如果不设置，1的next还是2，而2的next已经是1，就会形成循环链表。

内容的提问来源于stack exchange，提问作者Hank Tang