反转链表是数据结构里最经典的一道题也是一个绕不开的面试高频考点。题目本身很简单给你一个单链表让你把整条链表反转返回新链表的头节点。但正是这道看似基础的题能同时看出你对链表结构的理解、对指针引用的掌握以及边界条件的敏感度。我见过不少同学刷到几十道题后写反转链表还是会丢节点或者把链表弄成环。这篇文章我想从问题定义、迭代解法、递归解法、进阶变形到排坑实录完整拆一遍反转链表。无论你是刚接触算法的初学者还是准备面试想再巩固一遍这份梳理都很值得看。1. 反转链表是什么把“单向箭头”换成“倒着指”1.1 问题定义与示例反转链表的标准描述是给定单链表的头节点head反转整个链表并返回新链表的头节点。例如输入1 - 2 - 3 - 4 - 5输出5 - 4 - 3 - 2 - 1。这里的箭头就是每个节点的next指针链表的最后一个节点指向null。需要注意题目要求的是原地修改链表结构一般不希望你新建一个链表再重新拷贝。真正的考点是你能不能在不额外申请链表空间的情况下只通过调整节点之间的指针方向完成整条链表的逆序。很多刚接触的同学会尝试用一个数组把节点存下来再倒序串联这种方法虽然能过但面试时显然不是最优解。1.2 单链表的结构定义要理解反转先得清楚链表节点长什么样。以最常见的单链表为例每个节点一般包含两个字段存储数据的val以及指向下一个节点的next。用 Python 定义大概是这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextJava 版本的节点类也类似只是字段前需要声明类型。链表本身并没有数组那样的“下标”概念你拿到一个head其实只是一个引用指向第一个节点。想访问某个位置的节点只能从这个head开始通过next一路走。所以反转链表的核心操作对象是“指针”或者“引用”而不是节点的值。1.3 为什么不能像数组一样直接交换数组反转可以两端交换因为数组支持随机访问通过下标就能拿到任意元素。链表没有这个能力如果我想让尾节点变成头节点我必须从头遍历到尾如果我又想让原来的倒数第二个节点变成新的第二个节点又得从头遍历一遍。这样做的总时间复杂度会达到 O(n²)在链表长度稍大时性能非常糟糕。更麻烦的是如果只交换节点的val而不是调整next那么对于存储复杂对象或大对象的链表会带来额外的赋值开销而且逻辑上也绕。最干净的做法是只遍历一遍每经过一个节点就把它的next指针从“指向后一个节点”改成“指向前一个节点”。这样整条链表的箭头方向全部反过来反转就完成了。1.4 核心思路三指针模型用一个比喻来理解想象一排人前后排列每个人只牵着后面人的手。现在要让这一排人全部转身变成每个人都牵着前面人的手。你不能让所有人同时转身因为一转身就看不到原来身后的人是谁了。正确做法是每次只操作一个人并且在他转身之前先记住他身后那个人是谁。对应到链表里就是三个指针prev指向当前节点的前一个节点cur指向当前正在处理的节点nxt用来临时保存cur原本的后继节点。每一步的操作顺序固定先保存后继再改变当前节点的指向最后把prev和cur同时向后移动。这个三指针模型是迭代法的灵魂理解了它反转链表的基本盘就已经拿下了。2. 迭代法面试优先选它代码短且空间为 O(1)2.1 三个指针的分工与初始值迭代法需要三个指针prev前驱节点、cur当前节点、nxt后继节点。初始时prev必须是nullcur指向head。为什么prev不能是别的值因为反转之后原来的头节点会变成新链表的尾节点而尾节点的next必须是null。所以一开始就要让head.next指向null而这个“空”就是由初始的prev提供的。循环体内部一共四步操作保存nxt cur.next让cur.next prev把prev移动到cur再把cur移动到nxt。循环结束条件是cur null此时prev正好停在原链表的尾节点上也就是新链表的头节点直接返回prev即可。2.2 Python 代码实现与逐行解释这里给出标准 Python 实现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用手工推演一个三节点例子链表1 - 2 - 3。初始prevNonecur1。第一次循环nxt2把1.next指向nullprev变成1cur变成2。此时局部链表已经是1 - null2和3还没处理。第二次循环nxt3把2.next指向1prev变成2cur变成3。第三次循环nxtnull把3.next指向2prev变成3cur变成null。循环结束返回prev也就是3。整个过程刚好把所有指针方向调转。2.3 Java 版代码参考如果面试用 Java核心逻辑完全一样只是类型声明不同public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; }对比两份代码可以发现反转链表跟语言关系不大关键是你能否把三指针的移动顺序写对。尤其要注意nxt的赋值必须放在修改cur.next之前否则一旦cur.next被改写原来的后继节点就再也找不到了。这个顺序错一步整道题全错。2.4 复杂度分析与原地修改的意义迭代法只遍历链表一次所以时间复杂度是 O(n)其中 n 是节点数量。空间上只额外使用了三个指针无论链表多长占用空间都是常数级别因此空间复杂度是 O(1)。这也是工程上更推荐迭代法的原因不需要担心递归调用栈过深内存开销完全可控。“原地修改”意味着我们没有开辟任何新的节点只是在原有节点之间改指针。这样做的好处是省内存同时保持了节点本身的地址不变。面试官问你“为什么空间复杂度是 O(1)”你要能答出来因为三个指针都是固定大小的局部变量不会随输入规模增长。2.5 边界条件一个都不能漏这里单独强调边界条件因为我见过太多人在这些简单情况上翻车。最基础的测试用例有两个空链表和单节点链表。空链表时head是nullcur初始为nullwhile循环不会进入直接返回prev也就是null结果正确。单节点链表时cur指向唯一节点nxt是null执行完一次循环后cur.next指向nullprev变为这个节点cur变为null返回prev结果也正确。另一个容易错的地方是循环条件。有人会写成while (cur.next ! null)这会导致最后一个节点没有被反转原链表最后一个节点不会变成新链表的头节点。所以循环条件一定要是“当前节点不为空”而不是“下一个节点不为空”。3. 递归法代码更简洁但必须想清楚“从后往前”的路线3.1 递归思路先反转后面的链表再接上头节点递归法和迭代法的思考方向完全相反。迭代法是从头开始像推土机一样一步步把指针扭过来递归法则是假设“当前节点后面的链表已经全部反转好了”只需要再处理当前节点和它原本下一个节点之间的关系。核心逻辑可以写成三步第一如果当前节点是空或者当前节点的下一个节点是空直接返回当前节点这是递归出口第二递归调用reverseList(head.next)得到反转后的新头节点new_head第三让head.next.next head也就是让原本的下一个节点指回当前节点然后让head.next null断开原来的正向链接。最后返回new_head。3.2 代码实现与手工推演递归代码非常简单def reverseList(self, head: ListNode) - ListNode: if not head or not head.next: return head new_head self.reverseList(head.next) head.next.next head head.next None return new_head用1 - 2 - 3推演一遍调用reverseList(1)进入1.next2于是递归reverseList(2)进入2.next3再递归reverseList(3)此时3.next是null所以直接返回3。回到上一层head2new_head3执行2.next.next 2也就是3 - 2再让2.next null返回3。回到最外层head1new_head3执行1.next.next 1也就是2 - 1再让1.next null返回3。最终链表3 - 2 - 1。注意这个过程的巧妙之处递归到最底层后每一层返回的都是同一个新头节点3。而每一层做的操作都是让自己原本的后继反过来指向自己。这正好符合反转的定义。3.3 递归法的复杂度与栈溢出风险递归法的时间复杂度同样是 O(n)因为每个节点都会被访问一次。但空间复杂度是 O(n)而且这个空间来自调用栈的深度——每一层递归调用都会占用一个栈帧链表长度为 n 时递归深度就是 n。如果链表特别长比如几十万个节点就可能直接触发递归深度限制程序抛出栈溢出异常。Python 默认递归深度大约在 1000 左右所以非常长的链表并不适合用递归。面试时如果你写了递归最好主动补充一句“如果链表特别长递归可能栈溢出迭代法是更稳定的选择。”这一句话就能体现你对算法复杂度有完整的认识。3.4 递归 vs 迭代怎么选择用一张表把两种方法的关键差异整理清楚维度迭代法递归法思考方向从前到后从后到前时间复杂度O(n)O(n)空间复杂度O(1)O(n)代码行数略多但直观很短但抽象超长链表风险安全可能栈溢出面试加分点空间优势明显展现递归思维我的建议是面试中优先写迭代法因为 O(1) 空间是非常稳妥的答案如果面试官追问“还能怎么写”再补充递归法并顺带说明递归的空间代价。千万不要只背递归代码却解释不清每一步在做什么面试官很容易用“你大声讲一遍递归调用过程”来检验你是否真的理解。4. 进阶变体从逆序整个链表到逆序一小段4.1 反转部分链表核心是先定位前驱LeetCode 92 题要求反转从left到right之间的节点。例如链表1 - 2 - 3 - 4 - 5反转第 2 到第 4 个节点得到1 - 4 - 3 - 2 - 5。这道题不能直接把整条链表反转也不能用数组把区间存下来再倒序。正确的做法是先找到left位置的前一个节点pre以及left位置的节点leftNode。然后对以leftNode为头部的子链表做一次普通的反转但只反转right - left步。最后把pre.next接到反转后的头部把反转后的尾部接到原right后面的节点上。过程需要仔细画图尤其注意几个连接点不能接错。4.2 每 K 个一组反转分组反转与剩余处理LeetCode 25 题是另一个高频变体给你一个链表和一个整数 k每 k 个节点一组反转如果剩余节点不足 k 个就保持原顺序。比如链表1 - 2 - 3 - 4 - 5k2 时得到2 - 1 - 4 - 3 - 5。这道题可以递归求解先找到一个长度为 k 的区块如果找不到第 k 个节点说明剩余不足 k直接返回当前头如果找到了就把这一组 k 个节点用迭代法反转反转后原来的头变成这一组的尾部然后让它指向下一组递归反转后的结果。这样一层层做下去核心代码实际上就是“普通反转链表 递归连接”。4.3 双向链表的反转多一个指针多一步交换双向链表和单链表不同每个节点除了next还有一个prev指针。反转双向链表需要同时交换每个节点的prev和next。可以理解成原来head.next指向第二个节点反转后第二个节点的next应该回过头指向head原来head.prev是空反转后头节点的prev应该指向原来的第二个节点。实现时用一个cur指针遍历每次交换cur.next和cur.prev然后把cur移动到交换前的next节点。最后返回原链表的尾节点。这个知识点不是面试主流但如果你在简历里写了“熟悉链表”偶尔会被问到提前了解没坏处。4.4 反转链表还能引出哪些题反转链表经常作为其他题目的前置工具。比如判断回文链表时可以先找到链表中点反转后半部分再和前半部分比较比如两数相加时如果链表低位在前可能需要先反转链表再比如对链表做某种逆序合并时也绕不开反转这个操作。把这些相关题刷熟练后你会发现反转链表不是孤立的知识点而是一把通用钥匙。我建议学习顺序是先掌握完整反转再做部分反转然后做 K 个一组反转最后配合回文链表、两数相加这类题目巩固形成自己的链表解题框架。5. 实战排坑我在反转链表中踩过的几个坑5.1 空指针异常最常见的 Bug空指针异常通常出现在没判断当前节点是否为null就访问next的场景。比如递归法里有人会写成if not head.next: return head却漏了head为null的情况比如迭代法里采用while cur.next作为循环条件可能导致最后一个节点没被处理或者在循环体内误访问cur.next.next。解决思路很简单在每个方法入口先统一处理“空节点”判断再进入主逻辑。迭代法里坚持用while cur不要用while cur.next递归法里一定要写if not head or not head.next: return head。这样能挡住大部分空指针问题。5.2 链表成环问题链表成环是最恐怖的 Bug因为它不会马上报错而是让程序在打印链表时陷入死循环。常见的成环原因有两个一个是迭代时没有先保存nxt就直接修改cur.next导致后续节点丢失节点之间的关系混乱另一个是递归法里没有把head.next最终置为null使得原头节点仍然指向第二个节点而第二个节点经过反转后又指向第一个节点形成环。排查成环时可以写一个辅助函数打印每个节点地址以及它的next地址观察是否出现重复地址。如果打印到某个节点后又回到之前访问过的节点说明链表已经成环需要检查上述两处代码。5.3 边界测试用例清单刷反转链表时我习惯用下面这组测试用例来验证代码用例类型输入期望输出空链表nullnull单节点1 - null1 - null两个节点1 - 22 - 1多个节点1 - 2 - 3 - 4 - 55 - 4 - 3 - 2 - 1带重复节点1 - 2 - 1 - 22 - 1 - 2 - 1不要觉得这些用例简单就不测。越是简单的边界越容易被面试官追问。比如“你的递归对空链表会不会有问题”如果你提前准备好了回答就会很从容。5.4 写一个辅助打印函数调试效率翻倍在本地 IDE 或白板上调试时写一个打印链表的辅助函数非常有用。我分享一个简洁版本def print_list(node, limit10): count 0 while node and count limit: print(node.val, end - ) node node.next count 1 print(None)这个函数加了一个limit限制目的是防止代码有 Bug 成环时无限打印最多打印limit个节点就停止避免调试工具被卡死。实测下来调试反转链表时这个函数帮我快速看清每一步结果比单纯用断点还直观。5.5 典型错误版本速查错误代码特征后果修复方式循环里没有保存nxt后继节点丢失先把nxt cur.next用while cur.next作为循环条件最后一个节点未反转改成while cur递归出口漏了not head空链表报错改成if not head or not head.next递归结束没有设置head.next None链表成环一定要把head.next置空把这些错误类型记在心里写代码的时候主动规避比自己闷头调试十几次效率高得多。6. 几点过来人的练习建议反转链表这个题真的值得多写几遍。我自己的练习经验是第一天先背迭代法理解三指针移动第二天尝试不看代码自己默写第三天再练递归法并且对着纸模拟调用过程第四天开始做 92 题和 25 题这样的变体。这样循序渐进一周内基本能把这个知识体系彻底掌握。面试的时候记得先跟面试官说清楚思路再动笔。说清楚“我要用prev、cur、nxt三个指针每次让cur指向prev”比直接闷头写代码要加分得多。最后再分享一个小技巧反转链表之前先画一个 3 个节点的链表图把每一步指针变化都标出来这个过程会帮你避免掉至少一半的边界 Bug。这是我刷过上百道链表题后最真实的感觉希望这个方法也能帮你少走弯路。