反转链表：3步走通2种实现，迭代与递归一篇讲透

反转链表3步走通2种实现迭代与递归一篇讲透【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base反转链表Reverse Linked List是刷链表题绕不开的第一道关思路一听就懂但自己一写就总在手忙脚乱中把链弄丢。本文基于 algorithm-base 项目的链表篇教程带你先建立指针逐个掉头的心智模型再分别拆解迭代和递归两种实现最后给出选型建议和练习路线帮你把这道题真正变成基本功。30秒直觉用一句话建立心智模型反转链表就是从头走到尾边走边把每个节点的箭头拧到身后走完时最后一个节点自然成了新头。反转前1 - 2 - 3 - None 反转后None - 1 - 2 - 3 3 成为新头注意一个前提题目只允许修改节点的指向不允许改节点的值。所以倒着取节点拼一条新链这类思路是走不通的我们只能动箭头。方法A三指针迭代从前往后逐个掉头先看懂掉头这个动作大白话每个节点原本指向下一个人反转就是让它改口指向上一个人。做这件事只需要三个角色——prev已反转部分的头起点时是 None即新链表的尾巴cur当前正要掉头的节点nxt临时记住cur的下一个防止掉头后找不到路三个指针如何一步步推进以1 - 2 - 3为例跟着走三轮 看prev | cur的分隔线在哪初始 None | 1 - 2 - 3 - None prev cur 第1轮后1 掉头指向 None None | 1 | 2 - 3 - None prev cur 1.next None 第2轮后2 掉头指向 1 None - 1 | 2 | 3 - None prev cur 第3轮后3 掉头指向 2 None - 1 - 2 | 3 prev cur cur 走完变 Noneprev 停在 3它就是新头。整个过程prev永远走在已处理的一侧cur永远走在待处理的一侧两者的分界线每次后移一格这就是迭代反转的全部节奏。逐轮该做哪四件事每轮固定四步顺序不能乱nxt cur.next先记住下一个节点这一步不做链表当场断掉cur.next prev当前节点掉头指向已反转部分prev cur分界线右移当前节点并入已反转部分cur nxt进入下一轮Python 实现class Solution: def reverseList(self, head: ListNode) - ListNode: prev None # 已反转部分的头初始为空 cur head # 待反转部分的头 while cur: nxt cur.next # 1. 先存下一个防止断链 cur.next prev # 2. 当前节点掉头 prev cur # 3. 分界线右移 cur nxt # 4. 处理下一个节点 return prev # cur 走完prev 即新头空链表和单节点不需要特判循环要么不执行返回 None要么走一轮就结束返回唯一节点天然覆盖了边界。方法B递归从尾部开始才顺为什么先去尾巴换个角度看这道题如果让你从后往前处理反转反而很自然——最后一个节点不用动它就是新头倒数第二个指向它……难点在于单链表只能从前往后走而递归恰好能帮你先冲到尾巴。这就是递归写法的切入点把掉头推迟到回来的路上做。返回路上如何完成翻转还是以1 - 2 - 3为例下行递f(1) - f(2) - f(3) 3 是最后一个节点命中基准条件直接返回 3 上行归 回到 f(2)3.next 2然后 2.next None 得到 3 - 2 回到 f(1)2.next 1然后 1.next None 得到 3 - 2 - 1关键两行head.next.next head让下一个节点回指自己和head.next None切断旧方向防止两个节点互相指成环就是上行时每个节点要做的全部事情。逐行该做哪三件事命中基准条件head为 None 或只剩一个节点它自己就是子链的新头原样返回new_head self.reverseList(head.next)把剩下的事交给尾部拿到反转后子链的新头head.next.next head且head.next None把当前节点挂到子链前面并断开旧方向return new_head每一层都返回同一个最终新头保证最外层拿到的也是它Python 实现class Solution: 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迭代和递归的行数差不多但递归把记下一个节点、移动两个指针压缩成了一次调用和两行赋值读起来更紧凑。两种实现怎么选维度三指针迭代递归时间复杂度O(n)每个节点访问一次O(n)每个节点访问一次空间复杂度O(1)只用了几个指针变量O(n)调用栈深度等于链表长度出错风险点四步顺序别乱尤其先存nxt理解下行不动、上行才反转长链表表现稳定链表过长时可能栈溢出代码观感略繁琐但直白更紧凑选型建议默认写迭代。空间 O(1)、不怕长链机试和日常题里它最省心。递归适合两个场合面试官明确想听递归思路时以及后面要写 K 个一组反转LeetCode 25这类题时按组切分 递归下探的结构会比迭代好写很多。延伸两个常见的变形入口只反转一段LeetCode 92 反转链表 II。入口是定位 局部反转 重新接回先走到第left个节点前把left..right这段用上面的三指针法原样反转最后把断开的两头接回去。难点不在反转本身而在两头重接时别丢指针。项目里有对应的分步解析animation-simulation/链表篇/leetcode92反转链表2.md。K 个一组反转LeetCode 25。思路是把链表看成若干块每块凑够 K 个就整块反转凑不够保持原样。单块反转直接复用三指针法块与块之间递归处理。掌握 206 之后这道题的增量部分只是分组和拼接。动手练习路线先闭卷手写迭代版哪怕花二十分钟重点确认那四步的顺序能自己默出来对照动画自查打开项目里的 完整动画教程逐轮核对每轮结束后prev和cur的位置是否和你手写时推演的一致提交验证边界空链表、单节点、两节点三种输入各跑一遍再提交 LeetCode顺带把递归版默写一遍卡壳就回看下行不动、上行才反转那节更多链表题可以逛 animation-simulation/链表篇/反转链表这道题没有捷径就是把存下一个、掉头、移分界这个循环在脑子里过成肌肉记忆。接下来建议直接上手 LeetCode 92把局部反转的拼接练熟K 个一组反转水到渠成。【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考