企业官网建设流程全解析

反转链表：迭代与递归两种解法，含推演与复杂度对比

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base

模拟面试被问"反转链表"时，我写完迭代版，面试官追问"递归怎么写"，我愣了一下——当时只是背过代码，并没有想清楚指针在动什么。后来在 algorithm-base 项目里，配合白板推演和动画教程把两种解法重新走了一遍，才真正吃透。

反转链表的核心思想：把箭头逐个掉头

单链表可以看作一排"单行道"：每个节点只有一条出口——next 指针，指向下一站。反转链表并不改动节点本身，只是把每一条箭头的方向掉转过来：

原链表： 1 → 2 → 3 → 4 → NULL 反转后： NULL ← 1 ← 2 ← 3 ← 4 即： 4 → 3 → 2 → 1 → NULL

有两种做法：迭代是"从入口开始，一边前进一边把每段路掉头"；递归是"先一路走到尽头，回来时再逐个掉头"。前者只靠两个辅助指针原地完成，后者依赖调用栈来记住"已经反到哪儿"。下面分别推演。

链表反转三指针推演与迭代实现

用1 → 2 → 3 → 4做白板推演，准备三个指针：

• prev（初值 NULL）：已反转部分的头；
• cur（初值 head）：待反转部分的头；
• nxt（临时）：在修改cur.next前保存后面的节点，避免断链。

每轮核心操作就是四行：存nxt、把cur.next掉头指向prev、两个指针各前进一步。

初始： NULL 1 → 2 → 3 → 4 prev cur 处理节点1后： NULL ← 1 2 → 3 → 4 prev cur 处理节点2后： NULL ← 1 ← 2 3 → 4 prev cur

cur走到 NULL 时所有箭头都已掉头，此时prev恰好是新头。完整代码（Python）：

class Solution: def reverseList(self, head: ListNode) -> ListNode: prev, cur = None, head while cur: nxt = cur.next # 先存下一节点，否则改写 cur.next 后就找不到路了 cur.next = prev # 掉头：当前节点指向已反转部分 prev, cur = cur, nxt # 双指针前移，反转部分每次扩大一个节点 return prev # 反转后的头；空链表时自然返回 None

项目里的反转链表动画教程把整个过程做成了逐步演示，其中cur.next = prev执行的那一刻，正好对应推演表中"处理节点1后"这一步，可以对照着逐步验证。教程内还有 Java、C++、JavaScript、Swift、Go 五种语言的实现，写法结构一致，可一并参考。

递归反转链表调用栈分析

递归解法的关键是换到调用栈视角阅读：下探阶段什么都不做，一路钻到最后一个节点——这是基准条件，它直接作为反转后的头返回；回到阶段的每一层只做一件事："让下一节点指回我，我指向 NULL"。以1 → 2 → 3为例：

reverseList(1) # 下探 └─ reverseList(2) └─ reverseList(3) → 返回 3 # 基准情况：只剩一个节点，原样返回 3.next = 2，断开 2 → 3 # 回溯：3 掉头指向 2 2.next = 1，断开 1 → 2 # 回溯：2 掉头指向 1 返回 3 # 每层只透传头节点，不改变它

Java 实现（注意head.next必须在基准条件之后才允许访问）：

class Solution { public ListNode reverseList(ListNode head) { // 基准条件：空链表或最后一个节点，它就是反转链的头 if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); // 先反转后面的链 head.next.next = head; // 关键一步：让下一节点反过来指当前节点 head.next = null; // 断环：否则前后两节点互相指向成环 return newHead; // 头节点不随递归层数变化，原样向上透传 } }

有三个高频易错点值得单独记一下：

1. 忘记断环：head.next.next = head之后若不执行head.next = null，前两个节点会互为 next 形成环，链表将无法遍历。
2. 基准条件漏掉空判断：只写head.next == null时，传入空链表会直接空指针；必须同时处理head == null和单节点两种情况。
3. 返回值理解错误：每层递归返回的newHead都是同一个"原尾部节点"，而不是"本段反转后的局部头"，返回成head就错了。

两种解法的复杂度对比与选型

面试作答建议：先给出迭代版并讲清三个指针的职责，这能覆盖"常数额外空间"的追问；再补充一句"递归版本质是调用栈回溯时逐个掉头"，并主动说明它的空间开销是 O(n)。两个方案都给出后，选型问题基本闭环。

反转链表的变形题破题点

基础反转吃透后，常见变形都是同一套思路的封装，项目链表篇目录里有对应题目的动画可以对照：

• 区间反转链表（LeetCode 92）：用哑节点定位到left前一位置，对left到right这一段套用基础迭代反转，再把两端接回去。
• 只反转前 N 个节点：写一个只反转前 N 个节点的辅助函数，递归时逐层把反转部分的头返回给上层即可。
• K 个一组反转（LeetCode 25）：每次先预探 K 个节点判断够不够一组，够就反转该段并缝合首尾，不够则原样保留。

建议先在纸上默写两种解法，逐步对照项目里的动画检查指针状态，再开始刷变形题。下期讲讲链表的环检测与找环入口这两个经典问题。

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base