LeetCode 206. 反转链表：链表操作的第一课

题目：反转单向链表

LeetCode 206：给定单链表头节点 head，反转链表并返回新的头节点。

输入：1 → 2 → 3 → 4 → 5 → NULL
输出：5 → 4 → 3 → 2 → 1 → NULL

为什么这题是「链表第一课」：反转链表涉及链表操作的全部基本功——指针的重新赋值、赋值的顺序（先存再改）、头节点的更新、边界的处理——这四样在 K 个一组翻转（Hard）里同样存在——「简单的题练扎实的手」。

解法一：迭代三指针

核心思想：逐个节点「摘下来、接到新链表头」——三指针：prev（已反转部分的头）、curr（待处理的节点）、next（暂存后继）：

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # 1. 暂存后继（否则断链）
        curr.next = prev        # 2. 反转当前指针
        prev = curr             # 3. prev 前进
        curr = next_node        # 4. curr 前进
    return prev                 # prev 即新头

「赋值顺序」是唯一的坑：先改 curr.next = prev 再取 curr.next——后继丢失——整个链表断成两截——「先存后改」是链表操作的铁律——三指针的演变追踪（以 [1,2,3] 为例）：初始 prev=None, curr=1 → 第 1 轮：1.next=None，prev=1，curr=2 → 第 2 轮：2.next=1，prev=2，curr=3 → 第 3 轮：3.next=2，prev=3，curr=None → 返回 3——「逐轮追踪」是调试链表的最佳方法——纸上画图、每轮标 prev/curr/next 的位置——「画图」是链表题永不失手的工具。

解法二：递归

递归的核心思想：「反转以 head 为头的链表」= 「反转 head.next 为头的链表（子问题，信任它已完成）」+「把 head 接到子链表尾部」：

def reverse_list(head):
    if not head or not head.next:   # 递归基：空或单节点
        return head
    new_head = reverse_list(head.next)  # 信任：后面的已反转
    head.next.next = head           # 把 head 挂到子链表尾部
    head.next = None                # head 变成新尾
    return new_head

「信任传递」的思考方式：写递归时不要展开递归栈去追——「假设子调用已经正确完成」——只考虑「当前层与子问题的衔接」——head.next.next = head 这一行是精髓：子链表反转后，原来的 head.next 变成了子链表的尾——尾的 next 指回 head——head 接在尾部——「画两层递归展开图」验证一次（[1,2,3]：reverse(3) 返回 3 → reverse(2)：2.next.next=2 即 3.next=2、2.next=None → reverse(1)：1.next.next=1 即 2.next=1、1.next=None → 返回 3）——「验证一遍、信任永远」。递归的代价：O(n) 的栈空间（递归深度 n——链表长 10 万时栈溢出——「工程上用迭代、面试讲递归」——两个都要会。

延伸：哨兵与「反转的一部分」

哨兵节点的应用：反转链表不需要哨兵（头就是新头）——但「反转一部分」（LeetCode 92 反转链表 II：反转 [left, right] 区间）就强烈需要哨兵——「哨兵统一边界」：left=1 时（从头反转）没有前驱节点——哨兵让「区间前驱」永远存在——「哨兵让特例消失」是链表设计的通用技巧——LRU 篇的哨兵是同一思想。「反转一部分」的流程：找到 left 的前驱 pre → 区间内逐个头插到 pre 后 → 「头插法」的区间反转——「反转链表」的手法（头插）在分组翻转（库内 25 题）中反复出现。

「K 个一组翻转」的衔接：LeetCode 25 是 206 的 Hard 升级——「分组 + 组内反转 + 组间衔接」——组内反转就是本题的迭代三指针——「Hard 题是简单题的组合」——206 扎实，25 就只剩「衔接的细节」——链表的学习路径：206 → 21（合并）→ 141（判环）→ 25（分组）→ 460 附近的设计题——「每一步都站在前一步上」。

LRU 与设计题的进阶：组合设计的通用方法

LRU 与设计题的进阶：多数据结构组合的通用方法与更多设计题。「组合设计的通用方法」：「约束驱动的结构选择」：「逐个操作定复杂度」（get/put/put 其他——「每个操作的复杂度要求」列出——「单一结构的短板」（哈希缺序、链表缺定位、堆缺更新——「短板互补」——「结构的组合矩阵」（哈希+链表、哈希+堆、「双哈希」——「组合」的选型——「设计题的解法框架」：「操作→复杂度→结构→组合」四步。「更多设计题的盘点」：「LFU（460）」——双层结构（频率桶+同频链表——「minFreq 的维护」（淘汰时的定位——「LFU 的手写难度」一档——「MinStack（155）」（库内已有）——「辅助栈」的最小值同步——「Insert Delete GetRandom O(1)（380）」——哈希+数组+「随机索引的交换删除」——「删除的交换技巧」（末尾元素补位——「三结构的组合」——「 Shuffle 的 O(1) 删除」——「设计题家族」：155/146/460/380/707——「设计题的共同训练点」：「结构组合+边界处理+复杂度证明」。「链表操作的进阶技巧」：「哨兵的进阶用法」：「双向哨兵」（头尾各一个——「双向哨兵」的 LRU——「环形哨兵」——「哨兵的层级」（单向/双向/环形——「哨兵的家族」——「多级链表」（跳表的雏形——「跳表」（Redis zset 的实现——「跳表的层级」——「跳表 vs 红黑树」——「Skip List 的 O(log n)」——「概率性平衡」——「跳表」作为「链表设计的进阶」——「链表的宇宙」：哨兵→双向→环形→跳表——「每一步的扩展」都在解决上一层的局限。LRU 的进阶总结：组合设计的四步法（操作→复杂度→结构→组合）+设计题家族（155/146/460/380）的难度梯度+哨兵的层级进化（单向→双向→环形→跳表）——「LRU」作为设计题的「爷爷」，打开了「用数据结构组合满足复杂约束」的设计思维——「设计思维」是高级工程师与普通工程师的分水岭——「算法的设计题」训练的正是这种「约束下组合」的能力——它直接对应工程架构的日常：在延迟、成本、一致性、复杂度的约束下，选择与组合技术组件。

反转链表的高频问答：栈深、区间反转与 O(1) 空间的回文

问题一：递归版在真实环境里多长的链表会栈溢出？——Python 默认递归上限 1000 层，sys.setrecursionlimit 虽可调大，但底层 C 栈的容量不会跟着涨，调太高等于「把 RecursionError 换成段错误」；JVM 线程栈默认 512KB 到 1MB，每层调用帧几十到几百字节，几万到十几万节点的链表就有真实风险。所以工程结论明确：生产代码用迭代版，递归版的价值在训练「信任传递」的递归思维。想两头兼得，用显式栈模拟递归——把系统替你压的栈换成自己维护的栈，逻辑等价、深度可控——这也是所有「递归改迭代」的通用手法，树的中序遍历迭代化用的是同一个技术。面试时能主动报出「我的递归深度是 O(n)、长链表上会溢出」，比写出递归本身更能体现工程判断。

问题二：反转链表的中间一段（LeetCode 92）为什么强烈需要哨兵？——区间反转结束后要重新接驳：区间前驱的 next 指向新的区间头。当 left = 1 时，头节点自己就是区间头，它没有前驱——特判分支一多必错。哨兵让「前驱永远存在」，特例整体消失。实现的两个锚点：pre（left 的前驱）与 tail（反转前的区间头、反转后的区间尾），区间内逐个节点头插到 pre 之后，共执行 right − left 次。206 练的是单段反转的手感，92 练的是接驳与锚点——「反转」与「接驳」分开练熟，K 个一组翻转（LeetCode 25）就是两者的机械组合：先数够 k 个再动手（数不够保持原样），组内用 206 的三指针，组间用 92 的接驳——Hard 题在这里显出原形：它是 Easy 题的拼装。

问题三：回文链表（LeetCode 234）要求 O(1) 空间，和反转有什么关系？——标准解法是 206 的直接应用场景，三步组合：快慢指针找中点（慢针一次一步、快针一次两步，快针到头时慢针恰在中点）→ 反转后半段（迭代三指针原样复用）→ 前半与反转后的后半逐节点比较。可选第四步：把后半段再反转回去恢复原链表——工程上调用者还要用原数据时，恢复是基本礼貌；面试里主动提出「我会恢复现场」，是把算法题答成工程题的信号。这道题说明了链表学习的正确姿势：反转、找中点、合并、判环各自练成独立构件，难题只是构件的拼装——构件库里存得越全，看到新题目时的拆解越快。

问题四：反转还有「别的解法」吗？比如用栈？——有：全部节点依次入栈、再依次弹出重建 next——正确但 O(n) 辅助空间，与「原地」的惯例约束冲突；被问「还有别的写法吗」时，先给栈版、再主动指出空间缺陷、然后回到三指针，是展示权衡意识的完整回合。时间上 O(n) 已是下界——每个节点至少要访问一次、改一次 next，没有加速空间；真正的延伸在「换约束」：数据太大装不进内存时，用分块反转（每 k 个一块、块内反转、记录块间连接）按块读入写出，外存友好；链表换成带尾指针的双向结构，很多「反转」类操作退化为头尾指针交换。「最优」永远相对于约束成立——时间最优、空间最优、还是外存最优，约束换了答案就换——这是这道 Easy 题在问答环节里能挖出的最深一层。

小结

反转链表的完整解析：迭代三指针（prev/curr/next——「先存后改」的铁律——逐轮追踪调试）；递归两行（「信任子问题已完成」+ head.next.next = head 的衔接——O(n) 栈空间的代价——工程用迭代、面试讲递归）；哨兵的延伸（反转区间 II 的边界统一——头插法在分组翻转的复用）；学习路径（206 → 21 → 141 → 25——Hard 题是 Easy 题的组合）。给学习者的核心方法：链表题永远画图——纸上画节点和箭头，每一步操作更新箭头——「大脑模拟指针」容易错，「纸上的箭头」不会错——以及一个面试技巧：写完迭代版主动说「还有递归版，代价是 O(n) 栈空间」——主动展示多解与权衡，是面试的高分信号。

反转链表是「用代码操作指针」的第一课——它教会的不只是反转，是「在脑中维护多个指针的状态」——这个能力是所有链表、树、图操作的地基。