反转链表迭代与递归两种解法含推演与复杂度对比【免费下载链接】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 curcur走到 NULL 时所有箭头都已掉头此时prev恰好是新头。完整代码Pythonclass 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; // 头节点不随递归层数变化原样向上透传 } }有三个高频易错点值得单独记一下忘记断环head.next.next head之后若不执行head.next null前两个节点会互为 next 形成环链表将无法遍历。基准条件漏掉空判断只写head.next null时传入空链表会直接空指针必须同时处理head null和单节点两种情况。返回值理解错误每层递归返回的newHead都是同一个原尾部节点而不是本段反转后的局部头返回成head就错了。两种解法的复杂度对比与选型解法时间复杂度空间复杂度特点迭代O(n)O(1)指针一趟走完无栈开销内存受限场景的首选递归O(n)O(n)调用栈深度代码更短走到尾再逐个掉头是链题常用套路面试作答建议先给出迭代版并讲清三个指针的职责这能覆盖常数额外空间的追问再补充一句递归版本质是调用栈回溯时逐个掉头并主动说明它的空间开销是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/11/5 1:52:40 · 阅读 1.2k 反转链表：迭代与递归两种解法，含推演与复杂度对比
反转链表迭代与递归两种解法含推演与复杂度对比【免费下载链接】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 curcur走到 NULL 时所有箭头都已掉头此时prev恰好是新头。完整代码Pythonclass 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; // 头节点不随递归层数变化原样向上透传 } }有三个高频易错点值得单独记一下忘记断环head.next.next head之后若不执行head.next null前两个节点会互为 next 形成环链表将无法遍历。基准条件漏掉空判断只写head.next null时传入空链表会直接空指针必须同时处理head null和单节点两种情况。返回值理解错误每层递归返回的newHead都是同一个原尾部节点而不是本段反转后的局部头返回成head就错了。两种解法的复杂度对比与选型解法时间复杂度空间复杂度特点迭代O(n)O(1)指针一趟走完无栈开销内存受限场景的首选递归O(n)O(n)调用栈深度代码更短走到尾再逐个掉头是链题常用套路面试作答建议先给出迭代版并讲清三个指针的职责这能覆盖常数额外空间的追问再补充一句递归版本质是调用栈回溯时逐个掉头并主动说明它的空间开销是 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考