“每日一题”刷到链表反转这道题的时候很多人的第一反应是“不就是把指针掉个方向嘛”然后动手一写就发现要么链表直接断成两截要么运行超时要么返回的头结点不对。反转链表是链表操作里的经典题几乎出现在每一份算法面试题单上但它的价值远不止应付面试搞清楚反转链表等于把链表最核心的“指针修改顺序”这个基本功彻底打通了。这篇内容我会从题目本身讲起把迭代、递归两种解法的每一个细节拆开包括为什么三指针的顺序不能乱、为什么递归的head.next.next head能完成掉头、哪些边界条件最容易翻车再延伸到区间反转、K个一组反转这些经典变体。无论你是刚开始刷题的新手还是准备面试想查漏补缺这篇都能帮你把反转链表这块吃透。1. 反转链表到底在问什么一道题背后的链表本质1.1 题目描述与基本的输入输出约定原题要求很简单给定一个单链表的头结点head反转该链表并返回反转后的头结点。举个例子输入链表1 - 2 - 3 - 4 - 5输出应该是5 - 4 - 3 - 2 - 1。链表结点一般这样定义不同语言略有差异但核心字段一致class ListNode: def __init__(self, val0, nextNone): self.val val self.next next输入给的是头结点输出要求返回新链表的头结点。这个头结点很多人会写错反转之后原来的尾结点才是新头结点如果你最后返回的还是head那结果会变成1或者乱掉。题目本身没有额外限制但一个经常被忽略的隐含条件是链表长度可能是 0也可能是 1。这两种情况并不需要真的“反转”直接返回head就行。很多解法写到最后出 bug恰恰是没把这个特殊情况处理干净。1.2 为什么链表反转比数组反转难单向结构的“断链”风险数组反转有很多办法最无脑的是新建一个数组倒着填回去几分钟就能写完。链表反转却不能这么做虽然可以拷贝成数组再重建链表但那只是“看起来简单”面试里基本不会被认可。链表最大的特点就是“单向通行”每个结点只知道下一个结点在哪里不知道上一个结点是谁。想要反转两个相邻结点的指向比如让2指向1你必须保证在修改2.next之前已经把3的位置记录下来了否则2一旦指向1原来从2到3的联系就永久丢失了后面的结点全部变成“失联”状态。画个图感受一下。初始状态1 - 2 - 3 - null如果直接执行head.next.next head后面递归法会用到那2的 next 会被改成1但3就找不到了因为从头结点出发已经没有路径能到3了。这就是链表操作里最经典的“断链”。理解这个风险是掌握所有链表题的第一步。我自己的体会是链表题绝大多数 bug 都出在指针修改顺序上而不是逻辑不懂。每次操作前先问自己一句“我改了这条指针之后还有没有其他路径能到达剩下的结点”如果没有就先备份。1.3 “每日一题”该怎么刷先动手还是先想清楚很多同学刷“每日一题”的习惯是打开题解直接看代码看完觉得“懂了”合上又不会写。反转链表这道题特别适合用来纠正这种习惯因为它套路固定、解法清晰非常适合“先自己推演再写代码”的训练方式。我建议拿到题先不要看任何题解拿一张纸画一个三结点的链表然后自己想如果我有三个指针分别指向当前结点、前一个结点、后一个结点每一步该怎么动把这个过程在纸上完整走一遍再打开编辑器写代码。这样虽然慢但写出来的代码是你自己的面试时也不会因为紧张而卡住。这也是反转链表作为“每日一题”的价值所在它不考什么高深算法考的是最基础的“用指针操作结点”的肌肉记忆。这个肌肉记忆建立了后面做环形链表、合并链表、K个一组反转都会顺很多。2. 迭代解法三指针的“掉头”手术2.1 核心思路prev、curr、next三个指针的分工迭代解法是反转链表最主流的写法核心是三个指针prev指向当前结点的前一个结点初始为nullcurr指向当前要处理结点初始为headnxt记录当前结点的下一个结点防止断链每一步做的事情可以用一句话概括先把nxt保存下来再把curr.next指向prev然后三个指针整体后移一格。为什么要用三个指针而不是两个因为curr.next prev执行之后curr原来的 next 关系已经没了必须提前用nxt保存它否则循环无法继续。这个“先备份再修改最后移动”的顺序是整个迭代法的灵魂。2.2 代码实现与逐行说明下面是完整的 Python 实现也是我认为最简洁的版本def reverseList(head): prev None curr head while curr is not None: nxt curr.next # 先备份当前结点的下一个结点 curr.next prev # 当前结点指向前一个结点完成掉头 prev curr # prev 前进 curr nxt # curr 前进 return prev逐行拆解一下prev None头结点反转后要变成尾结点尾结点的next必须是null所以初始prev是None。curr head从头结点开始遍历。while curr is not None当前结点为空说明链表已经遍历完循环结束。nxt curr.next备份下一个结点这步不做的话第 5 行会丢失后续链表。curr.next prev让当前结点指向它前面的结点这就是“反转”的动作。prev currprev移动到当前结点。curr nxtcurr移动到原来保存的下一结点。返回prev循环结束时prev就是原链表的尾结点也就是新链表的头结点。Java 版本几乎一模一样class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nxt curr.next; curr.next prev; prev curr; curr nxt; } return prev; } }C 也差不多只是指针语法更明显能帮你加深“指针本身是变量next 是对象字段”这个区别class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* nxt curr-next; curr-next prev; prev curr; curr nxt; } return prev; } };2.3 手动画一遍全过程用 1 - 2 - 3 推演光看代码可能还不够直观我用1 - 2 - 3 - null完整走一遍迭代过程。这里假设每个结点用“值(指针)”表示初始状态prev null curr 1 链表: 1 - 2 - 3 - null第 1 轮循环nxt 2curr.next prev即1.next null链表变成1 - null同时2和3由nxt保存prev 1curr 2此刻实际状态prev 1 curr 2 nxt 2 临时视角: 1 - null , 2 - 3 - null第 2 轮循环nxt 3curr.next prev即2.next 1链表变成2 - 1 - nullprev 2curr 3第 3 轮循环nxt nullcurr.next prev即3.next 2链表变成3 - 2 - 1 - nullprev 3curr null循环结束返回prev 3也就是3 - 2 - 1 - null反转完成。建议你自己也在纸上画一遍重点关注第 4 行的nxt curr.next放在什么位置。很多人写成curr.next prev之后才去保存nxt这时原来的下一个结点已经找不到了。顺序错一步整个链表就断掉。这里补充一个实用经验如果担心自己记不住顺序可以默念口诀“先备份再掉头prev 跟上curr 走”。遇到类似的链表操作题这个节奏基本通用。3. 递归解法让调用栈帮你记住后续结点3.1 递归的终止条件与新头结点的传递迭代法的本质是“从前往后”逐个改指针递归法的本质则是“从后往前”改指针。很多初学者觉得递归难是因为它违背了人脑习惯的线性思考方式递归先一路走到链表末尾再在回溯过程中一层层反转。递归的终止条件写起来很简单if not head or not head.next: return head这个条件有两层含义not head空链表没有可反转的结点。not head.next当前结点是尾结点。递归调用会不断深入head.next直到尾结点才停止。关键在于递归函数的返回值是“反转后的新头结点”。尾结点就是新头结点每一层回溯都要把这个新头结点原封不动地往上传不能弄丢。很多人递归写不好就是把这个返回值理解错了以为返回的是当前层的某个结点。3.2 递归版代码head.next.next head 的深意先看完整代码def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_head最让人困惑的是这两行head.next.next head head.next None用1 - 2 - 3 - null来理解。假设递归已经深入到head 2这一层head.next是3head.next.next head等价于3.next 2这一步让3掉头指向2head.next None是为了断开原来的2 - 3防止成环关键点来了head.next.next head起作用的前提是head.next这个结点在递归返回后仍然可达。这正体现了递归与迭代的不同——迭代需要用nxt主动保存后继而递归由调用栈天然保存了每一层的现场。回溯过程中每一层都还握着自己的head.next所以即使2.next在下一轮才会被断开当前这一轮执行时head.next也就是3依然是可访问的。如果把执行过程拆成时间线reverseList(1)调用reverseList(2)reverseList(2)调用reverseList(3)reverseList(3)满足终止条件返回3回到head 2层执行3.next 22.next null返回new_head 3回到head 1层此时head.next是2执行2.next 11.next null返回new_head 3最终从3出发3 - 2 - 1 - null。3.3 递归 vs 迭代什么时候用哪个两种解法在多数面试官眼里都是标准答案但适用场景不太一样。下面用表格对比一下对比维度迭代法递归法空间复杂度O(1)只用了三个指针O(n)递归调用栈深度等于链表长度实现思路从前往后逐个改指针从后往前利用回溯改指针代码长度稍长但直观更短但理解门槛高链表过长时风险无额外风险链表很长时可能导致调用栈溢出面试追问点为什么先保存 nxthead.next.next 为什么不丢节点如果是面试场合我建议先讲迭代法因为空间复杂度更优而且不容易被追问“栈溢出怎么办”。但一定要把递归法也掌握因为很多面试官会问一句“能不能用递归写”或者反过来问“递归会不会溢出”你答不上来就会扣分。实际刷题时有个小技巧递归法一旦遇到“环”的需求就更容易乱比如后面要说的区间反转、K个一组反转迭代法反而更可控。建议以迭代法为主递归作为理解链表递归结构的补充。4. 最容易翻车的边界条件与调试技巧4.1 空链表与单结点链表很多人在这里丢分链表题有个共性边界条件对个数的要求不高但错一个就全错。反转链表的两个最基本边界是输入null空链表没有任何结点返回null输入单结点1 - null反转后还是1 - null返回该结点迭代法天然处理了这两种情况。空链表时curr None循环不执行返回prev None单结点时循环执行一次curr.next指向null返回prev 1正确。递归法同理因为终止条件里已经包含not head和not head.next。所以这两个边界其实不需要额外if判断前提是你的循环条件必须写对。常见的错误写法是while curr.next:这样遇到空链表会直接抛空指针异常因为curr本身是null访问curr.next就崩了。一定要写while curr:或者while curr is not None。4.2 防止循环链表末尾结点的 next 必须置空这是迭代法里最容易忽略的一步。如果最后忘记把原头结点的next置空会出现什么情况比如反转1 - 2 - 3在最后一轮循环中1.next已经在第一轮被改为null了所以迭代法通常不会成环。但递归法不同每一层都会执行head.next None这行一旦漏掉就会形成环。举个具体例子递归到head 2这一层时如果不执行2.next None那么从3出发回到2然后2还指向3链表变成3 - 2 - 3 - 2 ...死循环。测试用例如果链表长度稍微长一点程序会直接超时而且这种 bug 特别难查因为打印链表时可能会卡死。我自己的排查经验是反转类操作完成后一定要在返回前检查“反转后链表的尾结点”它的 next 是不是 null。如果是 null说明环路断开了如果不是说明某个结点的 next 没有处理好。4.3 调试技巧打印链表、断点观察指针关系链表题调试比数组题难因为你看不到“整条链”现在长什么样。推荐两个实用的调试方法。第一个是写一个简单的打印链表函数每次循环都打印当前状态def print_list(head): cur head parts [] while cur: parts.append(str(cur.val)) cur cur.next print( - .join(parts))在迭代法循环里加一行while curr: nxt curr.next curr.next prev prev curr curr nxt print(fprev{prev.val if prev else None}, curr{curr.val if curr else None})第二种是断点调试把nxt、curr.next prev这两行打断点单步执行观察每一步执行后curr和prev的关系。这一步能帮你直观地理解“先备份再修改”的必要性。这里再分享一个我踩过的坑链表题千万不要尝试用 JSON 序列化来调试循环引用会直接导致堆栈溢出。老老实实用“值 - 值 - 值”这种字符串拼接方式最稳也最直观。5. 从反转链表延伸出去面试与实战中的变体5.1 反转前 N 个结点、区间反转先会基础版再进阶反转链表本身是小菜面试官通常会往上加条件最常见的两种是“反转链表的前 N 个结点”和“反转链表从 left 到 right 的区间”。反转前 N 个结点可以借用迭代法的思路但要注意前 N 个反转之后原来第 N 个结点的 next 要指向第 N1 个结点这个衔接很容易漏。核心是记录两个关键位置first反转段的起始结点反转后变成尾结点它的 next 要接上下一段last反转前第 N 个结点反转后变成反转段的头结点区间反转更复杂一点需要引入“虚头节点”dummy node来统一处理 left 可能为 1 的情况。虚头节点是一个非常常用的链表技巧新建一个dummy结点让它的 next 指向原链表头这样无论从哪个位置开始反转都能用统一逻辑处理。最后返回dummy.next而不是head因为head可能已经被反转操作改变了。区间反转的实现思路是两段式先走到left位置的前一个结点记为pre在pre后面这一段执行“头插法”把每个结点依次插入到pre的后面重复right - left次这个“头插法”实际上就是反转链表的另一种形态每来一个新结点就把它放到最前面迭代完整个区间顺序自然就反了。5.2 K 个一组反转链表先会基础版再进阶如果在区间反转上再加难度就是“K 个一组反转链表”。题目要求每 K 个结点一组反转最后一组不足 K 个保持原样。这道题是反转链表家族里的天花板之一核心逻辑可以拆成三步用count判断剩余结点是否够 K 个不够则直接返回找到当前组的起始结点和结束结点按组反转将上一组的尾结点连接到本组反转后的头结点每一步都调用一次反转链表的子逻辑小组内反转就相当于普通反转。写这道题之前普通反转链表必须达到默写水平否则一旦出错根因很难定位。5.3 实际工程中的链表场景与刷题心态除了面试链表反转在工程里也有真实应用场景比如LRU Cache 等数据结构在结点移动时会用到链表指针重排文本编辑器撤销栈的链表式组织在页面回退时需要反转遍历顺序数据流中的逆序输出为了节省额外存储空间反转让空间复杂度从 O(n) 降到 O(1)不过坦率讲实际项目中直接用反转链表的场景不算特别高频它的价值更多体现在“训练指针操作思维”上。链表题教会你的不是某个具体 API而是“修改引用之前想清楚谁还持有旧引用”这种工程直觉。这种直觉在写缓存淘汰、处理事件队列、设计状态机时都很受用。刷题心态上我想多说一句不要因为“代码短”就轻视这道题。反转链表虽然核心代码只有几行但它几乎能覆盖链表题的所有基础考点。我见过很多同学刷了几百道题回头让他手写反转链表还是会忘掉nxt curr.next这一步原因就是当时只是“背代码”而不是“理解指针顺序”。把这道题彻底吃透后面再看环形链表、回文链表、链表排序你会觉得整个链表系列的“手感”一下子打开了。最后分享一个我个人的小习惯每过一段时间我会在草稿纸上重新手写一遍反转链表的迭代和递归解法不借助任何参考资料。写的过程中不需要犹豫、不需要试错就说明这个基本功还在。这个习惯我保持了很长时间成本很低收益却很大——无论面试现场状态多差反转链表永远是我的保底题。