反转链表是算法面试里出场率最高的题目之一LeetCode 206题的评论区几乎成了各家公司面试题的集合地。我第一次刷这题时觉得没什么难度结果手写阶段指针绕来绕去写出来的代码自己都看不下去。后来花了一整天把它彻底弄明白才发现这道题背后藏着链表操作最核心的一套基本功。这篇当作我Day 4的复盘笔记把反转链表的迭代法、递归法、头插法以及面试里常见的变体题和边界条件一次性讲透。准备面试的同学可以照着过一遍已经工作的朋友如果链表操作生疏了拿来温习也正合适。1. 面试官到底想考什么——反转链表的考点拆解1.1 链表的底层结构与反转的本质先回到最基础的问题链表到底是什么单向链表由一个个节点Node通过引用串起来每个节点至少包含一个数据域和一个指向下一个节点的引用next。头节点是链表的入口最后一个节点的next指向null。数组在内存中是连续的链表则是零散分布的节点靠指针连接这也是它叫“链”表的原因。反转链表的操作就是把每个节点next指针的方向调转原来是1 - 2 - 3 - null反转后变成3 - 2 - 1 - null。看起来就是改几个指针但实际做起来难点在于“改指针的先后顺序”。比如你把1的next从2改成了null那2这个节点就彻底找不到了链表还没反转就已经断了。所以必须先保存后续节点再修改当前指针最后移动指针继续处理。这个“先保存、再修改、再移动”的节奏不只是反转链表的核心也是几乎所有链表操作的核心。面试时如果考的是节点定义通常是这样的public class ListNode { int val; ListNode next; ListNode(int x) { val x; } }写题之前先确认数据结构不要一上来就写代码。很多面试官会故意把节点定义放在题目里就是看你会不会认真读题。1.2 为什么反转链表是面试高频题第一个原因它太基础了基础到任何语言、任何方向的岗位都可能问。后端问客户端问甚至一些偏数据方向的岗位也会拿它来热场。第二个原因这道题的实现非常考验代码严谨性。链表操作没有数组那种“天然下标”的便利所有访问都靠指针每一步都要想清楚当前指针指向谁、下一个该指向谁。第三个原因它给面试官留了足够多的追问空间——迭代写完了可以问递归递归写完了可以问能不能把空间复杂度降到O(1)再往深处引就是快慢指针、回文判断、区间反转、K个一组反转这些经典变体。一道题能串起十几个考点面试官当然爱用。1.3 面试中这题的三个隐藏考察点第一边界条件的处理。输入空链表能不能返回null只有一个节点的时候会不会出错这几乎是链表题最容易被扣分的地方。第二空间复杂度意识。用递归写反转代码很漂亮但空间复杂度是O(n)面试官追一句“能不能优化到O(1)”如果答不上来印象分会掉一大截。第三自测能力。写完之后能不能主动举例验证而不是等着面试官报测试用例这三个点做好哪怕代码不够简洁面试官给你的评价也会高一个档次。2. 迭代法三指针逐步反转2.1 核心思路先保存再改指向再移动迭代法最经典的写法是维护三个指针prev前一个节点、curr当前节点、next当前节点的下一个节点。每一步操作浓缩成三句话先用next保存curr的下一个节点防止丢失把curr的next改为prev让当前节点指向前一个节点三个指针整体后移继续处理下一个节点。用一个生活化类比来理解一排人排队每个人原本都看着自己前面那个人的后脑勺next指向队列前方。现在要整队反方向站你得让每个人先记住他原来前面是谁保存next再转身看向原来后面那个人反转指针然后自己往队尾方向走一步继续传达指令。任何人转身之前都必须先记住原来的“下一个人”否则队伍就断了。这个过程中还有一个关键的理解点prev的初始值是null。为什么不是head因为反转后原链表的头节点会变成尾节点而尾节点的next必须指向null。如果你把prev初始化为head最后链表会形成环测试直接超时。很多初学者的第一个bug就出在这里。2.2 代码实现与逐行讲解public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存下一个节点 curr.next prev; // 反转当前节点的指针 prev curr; // prev 前移 curr next; // curr 前移 } return prev; // 循环结束时 prev 就是新链表的头 }逐行拆解一下执行过程。初始时prev为nullcurr为原链表头head。假设原链表是1 - 2 - 3 - null第一次循环next保存21.next改为null链表断成null - 1同时2 - 3还连着prev移到1curr移到2。第二次循环next保存32.next改为1链表变成null - 1 - 2prev移到2curr移到3。第三次循环next保存null3.next改为2链表变成null - 1 - 2 - 3prev移到3curr变成null循环结束。返回prev新链表的头就是3。这段代码还有一个可以深挖的点叫“循环不变式”。每次循环开始前prev指向“已经反转好的链表的头”curr指向“接下来待处理链表的头”。这个不变量贯穿整个循环所以你最后可以放心返回prev。理解这个比背代码有用得多因为面试官会换各种方式考你只有真正理解指针状态变化的人才能应对。2.3 复杂度分析为什么是O(n)时间复杂度看循环次数链表的每个节点都会进入一次循环。循环里做的事情是常数规模的——保存引用、修改引用、移动引用没有嵌套循环所以时间复杂度是O(n)n是链表长度。空间复杂度看额外开销只用了prev、curr、next三个固定变量没有开数组、没有递归调用栈所以空间复杂度是O(1)。这里有一个细节值得注意如果链表有环上面的循环会不会死循环会的。curr会一直在环里转永远到不了null。所以面试时如果题目没有明确说链表无环可以先问一句“链表有没有环”或者在代码里主动加入环检测。这些是后面的变体题这里先不展开。2.4 边界条件与易错点边界条件本质上就三种但漏掉任何一种都可能翻车空链表head为null循环一次都不执行返回prev也就是null正确。单节点head.next为null第一次循环后prev指向唯一节点curr为null返回该节点正确。两个节点手动推一遍1和2反转后返回2别写错返回变量。最容易犯的错有两个。第一个是返回curr而不是prev。循环结束时curr一定是null返回curr就是返回空链表。这个错我见过太多人犯因为循环里一直在移动curr潜意识里觉得curr才是结果。第二个是忘记用next保存后继节点直接做curr.next prev结果下一个节点找不到了链表从中间断掉。提示写完后把“返回prev”这个动作作为检查点想想循环结束时prev指向什么、curr指向什么。想清楚这两个指针的最终状态返回值就不会写错。3. 递归法从最后一个节点往前想3.1 递归的思路把大问题拆成小问题迭代法是从链表头开始一个一个改递归法换一个视角反转1 - 2 - 3 - null可以拆成“反转2 - 3 - null再把1放到最后面”。而反转2 - 3 - null又可以拆成“反转3 - null再把2放到最后面”。一直拆到不能再拆也就是只剩一个节点或者空链表。这个思路用公式写就是如果head为null或者head.next为null返回head否则newHead reverseList(head.next)然后把head放到反转后链表的末尾head.next.next head最后把head.next置为null防止成环。很多人看不懂递归反转卡在“head.next.next head”这一步。拆开来看递归调用reverseList(head.next)返回之后newHead是“head的下一个节点开始反转后形成的链表的头”而head.next此时指向的节点正好是反转后链表的尾节点。所以head.next.next head的意思就是把原链表的头节点接到反转后链表的末尾。这个操作本质上就是“把当前节点放到最后”。3.2 完整代码与手把手思路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 - 2 - null手动走一遍调用reverseList(1)1.next不为null进入递归调用reverseList(2)reverseList(2)2.next为null直接返回2回到reverseList(1)这一层newHead 2执行head.next.next head也就是2.next 1执行head.next null也就是1.next null返回newHead即2。此时链表已经变成2 - 1 - null。整个过程里最关键的是理解递归栈的“返回”顺序先深入到底再逐层返回并修改指针。只要你把“当前层需要做什么”想清楚递归的代码就非常简洁。我自己刷题时凡是递归版本的链表题都会先在纸上画出递归返回的顺序再写代码出错率会低很多。3.3 递归法的空间开销递归不是免费的。每次递归调用都会在方法调用栈上压入一层栈帧保存当前的参数、局部变量和返回地址。反转一个n节点的链表递归深度就是n空间复杂度是O(n)。链表长度几千没问题但如果链表有几万个节点递归可能导致栈溢出。这是面试官最常在递归版代码后面追问的坑你需要在被问之前自己说出来。另一个细节是在Java中递归每层栈帧的开销比C稍微小一些但数量级一样是O(n)。不要因为测试用例比较小就忽略这个问题面试官考的是分析和工程权衡能力不是“能不能跑过”。3.4 面试中迭代和递归怎么选如果面试官没有特别要求我建议先说迭代法。理由有三点第一O(1)空间复杂度更符合工程化思维第二迭代法更接近底层指针操作能展示你对数据结构的掌控第三写出来更不容易出边界问题。但递归也不能完全不准备因为面试官很可能追问“你用递归怎么实现”来考察你的抽象能力。比较稳妥的做法是先写迭代AC之后主动补一句“这个题也可以用递归实现但空间复杂度会到O(n)”然后把递归版本讲出来。这样既展示了两种解法也说明你知道递归的代价面试官会觉得你思路完整。4. 换一种视角头插法实现反转4.1 头插法的思路每次把节点插到头部除了三指针迭代和递归还有一种思路也值得掌握头插法。它的想法是重新构建一条新链表遍历原始链表的每一个节点每遇到一个节点就把它插入到新链表的头部。最后一个插入的反而是第一个节点天然完成反转。头插法有两种写法一种是定义一个哑节点dummy另一种是直接定义一个null的新链表头newHead。我用后者代码更直观。这里要注意一个思维切换点迭代法的视角是“原地反转原链表”头插法的视角是“构建一条新链表不断往头部插入”。虽然代码长得像但讲出来的逻辑路线完全不同。面试时讲清楚这个差异往往比代码本身更让面试官认同。4.2 代码实现public ListNode reverseList(ListNode head) { ListNode newHead null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next newHead; // 当前节点指向新链表头 newHead curr; // 更新新链表头 curr next; } return newHead; }这个写法其实和三指针迭代非常像只是把它解释成“往新链表头部不断插入”。两者在内存上并没有本质区别因为都没有额外开节点。真正不同的地方在于思考方式头插法把“反转”重新解释成“不断把元素放到最前面”。这个视角在区间反转里格外有用因为区间反转需要“把区间内的节点逐个提到区间头部”本质上就是局部头插。4.3 三种写法对比方法时间复杂度空间复杂度核心思想适用场景迭代法三指针O(n)O(1)原地修改指针方向首选面试默认递归法O(n)O(n)拆子问题反向链接展示抽象思维头插法O(n)O(1)构建新链表头部插入理解前插逻辑区间反转常用三种方法的代码长度差不多迭代和头插的空间表现一样好真正拉开差距的是你对思路的讲解是否清晰。面试时不需要写出全部三种但至少要把其中一种讲透其余两种做到“被问到能马上写出来”。我在准备阶段会把三种版本各写两遍目的是让大脑形成多条检索路径面试时无论面试官从哪个角度切入我都能接住。5. 反转链表的变体题面试中的延伸5.1 区间反转只反转中间一段LeetCode 92题反转从第left个节点到第right个节点其余部分保持原样。这题被问得非常多因为区间反转是验证你是否真正理解了反转逻辑而不是背模板的试金石。核心步骤定义一个哑节点dummy指向head方便处理left等于1的情况用指针pre走left-1步停在left前一个节点从pre.next开始进行right-left次头插操作把节点逐个提到区间头部最后pre.next指向反转后的头原来的left节点的next指向right后面的节点。可以直接参考这段代码public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 1; i left; i) { pre pre.next; } ListNode cur pre.next; ListNode next cur.next; for (int i 0; i right - left; i) { cur.next next.next; next.next pre.next; pre.next next; next cur.next; } return dummy.next; }这段代码的循环内部做的是典型的头插每次把next节点从cur后面摘下来插到pre后面也就是当前区间的头部。重复right-left次整个区间就反转完成。写这题时最容易漏掉的是哑节点的使用。如果不加dummyleft等于1时pre没有前驱节点整个代码会变得非常别扭。面试时能用好哑节点本身就是加分项。5.2 每两个节点一组交换LeetCode 24题1 - 2 - 3 - 4变成2 - 1 - 4 - 3。这题的解法跟反转链表神似先处理前两个节点的交换再递归处理后面的链表。交换两个节点时同样需要用临时变量保存下一个节点不然一轮操作后指针就丢了。递归写法非常短public ListNode swapPairs(ListNode head) { if (head null || head.next null) return head; ListNode next head.next; head.next swapPairs(next.next); next.next head; return next; }很多同学做这题时容易在“交换后怎么接到后面的链表”上卡壳。关键是想清楚递归返回值和新链表头的关系。这里swapPairs(next.next)返回的是“从第三个节点起两两交换后的链表的头”把它接到head.next上再把next.next指向head两个节点的交换就完成了。这和递归法反转链表用的是同一个思维模式先处理子问题再把当前节点接到正确的位置。5.3 判断回文链表LeetCode 234题判断一个链表是否回文。常规做法是先用快慢指针找到中点再把后半段反转然后前半段和反转后的后半段逐个比较。这题把链表找中点、反转链表、指针比较三个基本操作串在一起是反转链表最常见的应用场景之一。具体步骤快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。然后从慢指针开始反转后半段。接下来两个指针从两端向中间移动逐个比较节点值。比较完之后如果你希望不修改原链表可以把后半段再反转回去如果面试官没有要求通常不需要还原但主动说一句“我可以把后半段反转回去恢复原链表”会显得你考虑周全。熟练之后你会发现反转不是目的“比较”“还原”“拼接”才是。面试官出这道题就是想看你能否把反转链表这个工具灵活用到其他问题上。5.4 反转链表在实际工程中的应用场景面试之外反转链表的思路在很多地方都有影子。比如LRU缓存中调整节点位置会涉及链表的摘除和重新插入类似头插法的逻辑比如文本编辑器的撤销重做底层用链表维护操作序列反向回溯时本质上就是“从后往前”遍历链表再比如路径回溯类算法中递归返回时需要逐层撤销选择和递归反转链表的“先深入再逐层处理”是同一个结构。当然绝大多数业务开发不会真的手写反转链表这种数据结构级的操作通常被封装在标准库里。但掌握指针操作会让你在排查疑难问题时多一层直觉。尤其是遇到“容器内部实现导致性能退化”这类问题时理解链表的内存布局和指针变化比只会调用API更能精准定位问题。5.5 一道必会的综合题K个一组反转LeetCode 25题K个一组反转链表。这道题把链表反转和边界处理都拉满了先判断剩余节点是否够K个不够就直接返回够的话反转这一段然后递归处理后面的链表。很多公司的高频题里都有它因为它不仅考反转还考“分组”这个概念怎么和递归配合。不建议刚学完基础反转就硬刷这题先把区间反转练熟再上手K个一组。刷的时候注意两点一是反转每一段时要保证末尾节点正确指向下一段的开头二是判断剩余节点是否够K个需要先走K步检查不够就停。这个“先探路再操作”的模式在链表题里经常出现值得单独练。6. 常见问题与排查技巧实录6.1 常见错误与排查思路我把自己刷题和带人时见过的问题整理成一张表错误现象可能原因排查思路运行死循环反转后存在环可能某次操作没有把next置null检查head.next null这一步是否遗漏返回结果是null循环结束时返回了curr而不是prev用两个节点的链表手动推导一遍反转后链表丢失后半段修改指针前没有保存next确保每次循环先执行next curr.next递归写法栈溢出递归深度太高或终止条件写错检查终止条件是否处理了空和单节点长链表改用迭代反转结果顺序不对指针移动顺序反了画图标出每一步的指针位置变化排查链表问题最忌讳盯着代码硬看。正确姿势是把链表缩到最小规模用纸笔画每一步的指针状态。画三步基本就能定位问题。我在面试辅导中见过很多人看半天代码看不出问题一画图立刻就发现是自己把prev和curr的赋值顺序搞反了。6.2 链表题的调试小技巧第一写一个打印链表的方法。很多链表题看不到中间状态打印出来一目了然。我刷题时经常在方法里临时加一行System.out.println查看反转到中间某一步的状态确认逻辑后再删掉。第二用小规模数据验证。空链表、单节点、两个节点、三个节点这四种情况测过之后90%的边界bug能暴露。第三善用哑节点。处理需要改动头节点的操作时定义一个dummy节点能让代码少很多边界判断尤其适合区间反转这类需要定位前驱的场景。调试时还会遇到一个常见的心理陷阱测试通过了就觉得万事大吉。链表题真正要验证的往往是你主动构造的边界用例而不是系统给的普通用例。比如反转链表普通用例是3个节点但你一定得手动测一下空链表和单节点这两个用例最容易暴露返回值写错的问题。6.3 面试现场的经验心得这道题在面试里出现频率极高我在实际准备中总结出几条经验。首先写代码之前先把思路说出来哪怕只是简单一句“我用三个指针先保存下一个再改当前指针”面试官就能跟着你的节奏走也会更宽容你的小错误。其次写完之后主动做一次自测不要等面试官给用例自己拿一个链表举例大声说出每一步指针的变化。这个动作极其加分它说明你不是在背代码而是真的理解算法在做什么。最后再提一个细节面试中如果时间允许把复杂度分析主动说出来时间复杂度O(n)、空间复杂度O(1)大多数情况下到这里就够了。如果面试官追问“能不能不用递归空间”之类的问题直接用前面第2节的迭代法思路回答把递归的空间代价和迭代的O(1)优化讲清楚即可。我个人在实际操作中的体会是反转链表这道题不难但极其适合作为链表题目的起点因为它把指针操作、边界处理、递归思维三个最核心的东西都包含了。刷完这题之后我建议你立刻把区间反转、两两交换、回文链表这三道变体刷一遍你会发现它们之间有很多共通的地方。等这些题都掌握了再看K个一组反转也不会觉得离谱。如果你手边正好有链表题做得吃力反转链表就是你最应该死磕的那块基石。