LeetCode 206. 反转链表：迭代、递归与「纸牌串」直觉

反转链表是链表世界的「乘法口诀」：它本身是 LeetCode 206 这道简单题，却也是一整族链表题（92、25、234、143……）里反复调用的子程序。这篇按本栏目「每篇讲透一道题」的惯例，把迭代、递归两种解法逐行拆开，重点讲清两个最容易含糊的地方：迭代时为什么要先存 next，递归时 head.next.next = head 这行「回头指」到底发生了什么。文中两版代码均已本地跑通（含空链表、单节点边界用例）。

一、题面与约束

LeetCode 206「反转链表」（难度：简单）：给定单链表的头节点 head，反转整个链表，返回反转后的链表。

输入	输出
head = [1,2,3,4,5]	[5,4,3,2,1]
head = [1,2]	[2,1]
head = []	[]

官方约束（以 2026-10-07 力扣官方题目页为准）：

• 链表中节点数目范围是 [0, 5000]；
• -5000 <= Node.val <= 5000。

进阶：链表可以选用迭代或递归方式完成反转，你能否用两种方法解决这道题？——这正是本文的主线。另外注意节点数下限是 0：空链表是合法输入，base case 与循环入口都必须天然兜住它。

二、迭代：把纸牌一张张插到新串头上

逐行走一遍

直觉类比：左手握着旧串（原链表），右手在攒新串（反转结果）。每一步从旧串头上摘一张牌，插到新串头部——摘到最后，整串自然倒序。维护两个指针：

• prev：新串的头（已攒好的部分），初始为 None——新串从零开始；
• curr：旧串当前的头（下一张待摘的牌），初始为 head。

循环体四行，做的事是三件：先存 next、反向指、双指针各前移一步。

prev, curr = None, head
while curr:
    next_node = curr.next   # 先存：记住旧串剩下的牌
    curr.next = prev        # 反向：摘下 curr，插到新串头部
    prev = curr             # 新串头指针移到刚插的这张
    curr = next_node        # 旧串指针后移，处理下一张
return prev                 # curr 为 None 时旧串空了，prev 即新头

这个类比里还藏着一个容易被忽略的选择：为什么新牌总是插在头部，而不是从尾部接？因为单向链表只有 next 一个方向，「头」是我们唯一能 O(1) 插入的位置；若每张牌都从新串尾部接，就得每次从头走到底，整趟反转退化成 O(n²)。从头上插这个动作，恰恰把「只能顺着 next 走」这个限制变成了武器。

迭代进行到 curr 走到节点 3 时，局面是这样：

新串   2 -> 1 -> None          prev 指向 2
旧串   3 -> 4 -> 5 -> None     curr 指向 3

执行完这四行，节点 3 被摘下插到新串头：

新串   3 -> 2 -> 1 -> None     prev 指向 3
旧串   4 -> 5 -> None          curr 指向 4

整串走完，prev 停在节点 5 上，5 -> 4 -> 3 -> 2 -> 1 -> None 就是答案。

最常见的错误：不存 next 就改指向

第一行「先存」看起来像多余的仪式感，其实是保命符：curr.next = prev 会覆盖 curr 原本指向的「旧串剩余部分」，不先把 next 存进局部变量，从 curr.next 往后的所有节点就永远失联了——链不是「反」了，是「断」了。因果关系一张图：

flowchart TD
    A["想执行 curr.next = prev 摘牌插头"] --> B{"旧串剩余的引用存好了吗"}
    B -- "先存 next_node" --> D["旧串由 next_node 接管，新串多一张牌"]
    B -- "没存直接改指向" --> E["旧引用被覆盖，后半段全部失联，断链"]

记住这条纪律：动 next 指针之前，先用局部变量保住要去的地址。递归解法里两行的先后顺序，本质是同一条纪律。

三、递归：一行「回头指」完成反转

逐行走一遍

递归的思路是把问题缩小一圈：「反转以 head 开头的整串」等价于「先反转 head.next 开头的子串，再把 head 接到结果的尾部」。

def reverseList(self, head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head              # 空串或最后一个节点：它就是新头
    new_head = self.reverseList(head.next)  # 后面的整串已反转好
    head.next.next = head        # 回头指：子串的新尾掉头指回 head
    head.next = None             # head 成为新尾，断开旧指向
    return new_head

递进到末尾：reverseList(5) 命中 base case 返回节点 5；此后每一层回溯时，new_head 都原样上交、始终是 5——新头在递归最深处就定了，上层只负责接尾巴。

「回头指」为什么能反转

关键在回溯瞬间 head.next 仍指向原后继。以 head = 节点 2 这层为例：递归调用返回后，3 -> 4 -> 5 已反转为 5 -> 4 -> 3，但 2.next 还指着 3。此时节点 3 恰是已反转子串的尾，head.next.next = head 就是让这个尾掉头指回 2——2 被接到新串末尾。而 head.next 是此刻找到 3 的唯一凭据，所以这行必须赶在覆盖它之前执行。

用最小的 1 -> 2 -> 3 走一遍更直观：递归压栈到 reverseList(3) 命中 base case 返回节点 3；回到节点 2 这层，执行 2.next.next = 2 让 3 掉头指 2，再 2.next = None，此刻后半串是 3 -> 2 -> None；回到节点 1 这层，执行 1.next.next = 1 让 2 掉头指 1，再 1.next = None，得到 3 -> 2 -> 1 -> None——new_head 全程就是最初递到底摸到的节点 3。

置空的时机：防环，也防丢引用

接着 head.next = None：2 成为新串的尾，尾部必须收口。这行省不掉——不置空的话 2 指 3、3 又指 2，整串出现一个二节点环，遍历永远出不去。顺序更不能颠倒：先置空再想用 head.next 找后继，就是空指针。先用旧引用（回头指），再覆盖它（置空），与迭代里「先存 next」完全同构。

O(n) 栈空间不只是理论账

递归每层栈帧存一个 head，深度等于链表长度，额外空间 O(n)。这笔账在本题约束下有具体数字：节点最多 5000 个，而 CPython 默认递归深度上限是 1000（sys.getrecursionlimit() 的默认值）——本地实测 n = 5000 的递归版直接抛 RecursionError，手动调高上限后才正常输出；同一规模下迭代版毫无压力。各判题环境可能调高过默认上限，但工程代码不该赌环境。

四、复杂度对比与工程选择

解法	时间	额外空间	备注
迭代	O(n)	O(1)	两个指针加一个暂存变量，原地反转
递归	O(n)	O(n)	栈深度与链表长度成正比

时间上两版都是 O(n)——每个节点恰好被「摘插」或「回头指」一次。工程上选迭代，理由按权重排：

1. O(1) 对 O(n)：链表长度不受递归栈深度约束，5000 个节点与 500 万个节点一样稳；
2. 无爆栈风险：不依赖运行时的递归上限设置（Python 默认 1000，远小于本题 5000 的约束上限）；
3. 可读性不输：迭代版是「三件事 + 一个循环」的心智模型，递归版的「优雅」并没有换来更少的理解成本。

递归版的价值在思维训练：把「回头指」一行想透，回溯型链表题（如两两交换链表节点）就都有了抓手。

五、完整验证代码

两个类各含一版 reverseList，构造 1->2->3->4->5 与边界用例（空链表、单节点、两节点）逐一对拍，已本地跑通：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:                      # 迭代版
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr:
            next_node = curr.next    # 先存：保住旧串剩余部分
            curr.next = prev         # 反向：摘牌插到新串头
            prev = curr              # 新串头前移
            curr = next_node         # 旧串头后移
        return prev


class SolutionRec:                   # 递归版
    def reverseList(self, head: ListNode) -> 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


def build(vals):
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


if __name__ == "__main__":
    for vals in ([1, 2, 3, 4, 5], [1, 2], [], [7]):
        assert to_list(Solution().reverseList(build(vals))) == list(reversed(vals))
        assert to_list(SolutionRec().reverseList(build(vals))) == list(reversed(vals))
        print(vals, "->", to_list(Solution().reverseList(build(vals))))
    print("all passed")

本地实测输出：

[1, 2, 3, 4, 5] -> [5, 4, 3, 2, 1]
[1, 2] -> [2, 1]
[] -> []
[7] -> [7]
all passed

变体延伸一句：把「反转全部」换成「反转前 n 个」（LeetCode 92 的前置基本功），只需把「走到 None」的循环条件改成「数到 n」，再留意把反转段与剩余后缀接回——同一套指针纪律，此处不展开实现。

六、同族题地图

反转链表是大量链表题的「子程序」，写熟之后它们只剩下组装：

• 92. 反转链表 II（中等）：反转区间 [left, right]——先定位 left 的前驱，区间内做一遍 206 的摘插，再与前缀、后缀接回；
• 25. K 个一组翻转链表（困难）：每 k 个一组调用反转子程序再拼接，本质是 206 的套娃；
• 21. 合并两个有序链表（简单）：双指针在链表上的另一块基本功，dummy 头结点技巧与本文的 build 函数同源；
• 234. 回文链表（简单）：快慢指针找中点 + 反转后半段再比对，206 直接当子程序调用；
• 143. 重排链表：找中点、反转后半段、两段交错合并——三步里两步是本文内容。

参考资料

1. 206. 反转链表 - 力扣（LeetCode）
2. Reverse Linked List - LeetCode
3. 206. Reverse Linked List - leetcode.ca
4. 0206. 翻转链表 - 代码随想录
5. 92. 反转链表 II - 力扣（LeetCode）