有一道题看起来不超过十行却常年挂在算法面试和在线判题平台的热门榜单上那就是反转链表。我见过不少朋友在数组上玩得很溜交换两个元素用中间变量一气呵成可一碰到链表就莫名发怵数组可以通过下标定位任意位置链表呢你手里只有一个头节点既访问不到“上一个节点”也没法倒着走。更扎心的是这道题即使照着答案背下来过半个月再写十有八九还是会丢一个指针。这篇文章就专门把反转链表两种解法讲透三指针迭代版和递归回溯版。我会把每一步为什么这样做、边界条件为什么重要、两种写法各自的代价都说明白最后再补上反转前 K 个、区间反转、K 个一组翻转这几个高频变体。不管你是刚学数据结构的新人、准备面试的求职者还是工作中偶尔被链表逻辑绊住的工程师都能把这套思路直接拿去用。先把丑话说在前面反转链表不是一道“背代码”的题。背模板当然能应付一次两次但面试里稍微加一点点变形比如只反转中间一段或者 K 个一组反转很多人又懵了。原因很简单——没有真正理解“指针”和“引用”在链表这个结构里的流动方式。所以我这篇不打算直接甩答案而是从数据结构本身开始推演你跟着走一遍后面变体题自然迎刃而解。1. 先搞清楚一件事反转链表到底在反转什么很多错误代码的根源是对“反转”这件事的理解太模糊。先把最基础的模型摆清楚后面所有解法都建立在这一点上。1.1 单链表的存储结构与遍历约束单链表的一个节点通常只有两个字段一个是值一个是next引用指向下一个节点。最后一个节点的next为null表示“到此为止”。用 Java 定义大概是这样的public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }这里的核心约束只有一条顺着next只能从前往后走。这是单链表和数组最大的差异。数组的每个元素自带下标你想访问第 5 个元素用下标一下就到链表想访问第 5 个节点你必须从head开始沿着next跳 4 次。所以任何需要回头访问的算法链表都不能靠“天然能力”必须自己额外保存引用。很多人写反转链表卡住本质上是习惯了数组思维。数组翻转可以一个循环里用左右两个下标互相换因为两个下标都能立刻索引到目标元素链表里你想让当前节点的next指向它的前驱就必须提前把前驱保存下来——否则当你执行完这一步当前节点和后继的通道就断了整条链表后半段直接失联。1.2 反转的本质把 N-1 条 next 箭头整体换向假设链表长度是 N节点依次是 A1、A2、……、An。反转之后新链表的顺序是 An、……、A1返回的头节点应该是 An。从物理连接上看我们需要做的就是把相邻节点之间的 N-1 条next箭头全部掉转方向A1.next 不再指向 A2A2.next 不再指向 A3等等同时A1.next 要从指向 A2 改为null表示新的链尾。而 An.next 原本是null反转后 An 变成头节点它的next指向 An-1。这里有个容易被忽略的点虽然有效箭头是 N-1 条但实现时你可能要改动 N 个节点的next字段因为要处理头节点变尾节点时的那个置空操作。为什么强调这个因为很多错误版本就是只改了中间几条箭头忘了把原头节点的next置空结果链表里出现一个环遍历时就死循环了。理解这一点你就可以给自己一个验收标准反转完成后从返回的节点开始沿着next走 N 步能依次经过 An、An-1……A1并且第 N 步走到的节点的next必须是null。1.3 判断反转题做得对的三个标准我平时带新人时会让他们用一个朴素的办法检验答案不要光看用例输出对不对而是手写三个用例跑一遍并且自问三个问题。第一结果顺序对不对。把原链表打印出来反转后再打印必须完全逆序。这个看似废话但有些人会在“把最后一个节点提上来”和“整体逆序”之间混淆反转区间变体里最常犯这种错。第二有没有丢节点。反转之后链表里的节点数量必须和原来一致。你可以在调试时打印每个节点的值数一数。如果有节点凭空消失八成是某个指针没保存修改next的时候把唯一引用覆盖了。第三边界对不对。空链表反转完还是空只有一个节点的链表反转完还是它自己两个节点的链表反转完要互换位置。这三种情况是最容易写出 bug 的后面每一版代码我都会对着它们验证。2. 解法一三指针迭代翻转先学会把箭头掰弯迭代版是工程上最常用、也最推荐掌握的反转链表解法。它的思路一句话就能说清一边从头遍历一边把当前节点的next反向指向它的前驱。2.1 核心操作拆解断链、换向、推进由于单链表没有回头路我们必须始终知道三样东西当前节点是谁cur、前一个节点是谁prev、下一个节点是谁next。其中next最重要也最容易丢。为了说得具体我们看一个长度为 3 的例子1 - 2 - 3 - null。初始时prev nullcur 1。反转第一个节点时先保存next 2然后把1.next从原本指向 2 改成指向prev也就是null——这一步之后1 暂时成了“孤家寡人”但 2 和 3 还因为我们保存的next引用而安全。接着prev变成 1cur变成 2进入下一轮。第二轮保存next 3把2.next从指向 3 改成指向 1第三轮保存next null把3.next改成指向 2。最后cur变成了null循环结束prev正好停在 3 上这就是新链表的头。整个过程你可以想象成一排人面朝右站你站到队尾让每个人转身朝左同时保证转身时有人拉着后面的人不让队伍散掉。prev就是你已经整理好的那部分队伍的头cur是当前正在转身的人next是后面还没转身的那一列。三个引用缺一个队伍都会断。2.2 代码实现与循环不变量直接看完整代码public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 先保存后继防止断链 cur.next prev; // 箭头反转向左 prev cur; // prev 前进 cur next; // cur 前进 } return prev; // 原链表的尾节点就是新链表头 }循环不变量是这段代码的灵魂。每次进入循环时prev指向已经反转完毕的那一段链表的头最初为空链表所以是nullcur指向当前待处理的节点从cur到原链表末尾的节点保持原样。循环体内做的事只有一件把cur从“未处理队列头部”挪到“已反转队列头部”。这个不变量想清楚之后返回值就不需要纠结了——循环结束时cur null意味着所有节点都处理完了prev自然就是反转后的头节点直接return prev即可。还有一个写代码的细节为什么先保存next而不是先改cur.next因为cur.next一旦被赋值成prev原本的cur.next就没人知道了。除非你在改之前把它放进一个变量里。这个顺序问题是迭代法里最容易踩的坑。2.3 迭代法最容易丢节点的三个瞬间第一种错误忘了保存next。直接写cur.next prev然后prev cur; cur cur.next;——第二句的cur.next已经是prev了cur再也没法往前走要么死循环要么后面链表整个丢掉。正确做法必须先把next存下来再动cur.next。第二种错误循环条件写成while (cur.next ! null)。这样最后一个节点永远不会进入循环体它的next不会被改掉返回的prev是倒数第二个节点等于少反转一个节点。正确条件是while (cur ! null)让每个节点都过一遍。第三种错误忘记初始化prev为null或者返回时返回了head而不是prev。返回head的话此时head的反转工作只做了一半甚至head已经变成链尾了拿它当新头等于把整个反转结果折成两段。记住新头永远是原链表的尾也就是循环结束后的prev。如果题目还有附加条件“只能更改节点的next指针不能更改节点中的值”那数组翻转里常见的“交换值”把戏同样不可行必须用这种纯指针搬运的方式。这一点在面试里经常被追问提前想明白能省很多解释。3. 解法二递归回溯把反转当成“每一层只处理一对相邻节点”递归解法第一次看可能觉得玄幻但它其实是“分治”思路最直观的体现。我们要反转一个链表可以直接问自己如果我把头节点之后的部分先反转完再处理头节点和这一部分的关系行不行答案是可以。3.1 递归基与子问题定义子问题是这样的对head.next这个子链表调用reverseList(head.next)它会返回从原第二个节点开始、一直到最后节点的反转后的头。比如原链表1-2-3那么reverseList(2)会返回 3并且把 2 和 3 之间的箭头改成3-2。这层调用返回后原链表的第二个节点 2 就是整条链表“已反转部分”的尾而head也就是 1 还孤零零地挂在前面它的next仍然指着 2。接下来要做的事情只有两件让2.next重新指向 1再把1.next置空。这样整条链表就变成了3-2-1。递归基怎么写if (head null || head.next null) return head;。head为null对应空链表head.next null说明当前只有一个节点反转一个节点还是它自己不用继续递归。为什么这个基合理因为一个节点不需要做任何指针修改直接返回即可这是递归终止的底线。3.2 回溯时 head.next.next head 为什么能成立很多人卡在head.next.next head这行看不懂。一步步拆对当前层来说head表示当前递归函数接收到的子链表头经过内层递归返回后head.next这个引用并没有变化——它仍然指向原来的下一个节点只是这个节点的next可能已经被内层递归改掉了。此刻我们要把当前节点的箭头反过来让它的原后继指向它自己所以写head.next.next head。这行代码翻译过来就是“我头节点原来的下一个节点现在请你把next指向我”。为什么可以因为head就是head.next的前驱这正是反转需要的连接。接着执行head.next null。有人会问如果把head.next置空那之前head.next.next head建立起来的新连接会不会被破坏不会。head.next指向的还是同一个节点对象我们只是修改head节点自己的next字段至于那个节点对象的next字段指向哪里跟head.next这个引用本身无关。所以这一步只是把原链表的头节点变成新链表的尾节点让链表的终点正确落在null上。想验证这一点强烈建议在纸上画三个方框代表 1、2、3用箭头标注next的变化。从最内层开始往回推你会发现在每一层其实都在重复同一个动作让后一个节点指向当前节点再让当前节点指向null。子问题相同动作相同这就是递归能成立的根本原因。3.3 递归版代码与递归栈可视化完整代码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-3走一遍调用栈调用层收到的 head递归行为返回后执行返回值第1层1调用 reverseList(2)2.next 1; 1.next null3第2层2调用 reverseList(3)3.next 2; 2.next null3第3层3head.next null直接返回无3注意newHead从最深层一路往上传每一层都原封不动地把它返回出去所以最终的返回值一定是原链表的尾节点。这也是递归版不用像迭代版那样维护prev的原因——新头由递归返回值天然决定。4. 两种解法不是二选一复杂度与工程选择的账要算明白面试最爱问的一句话是“你还有别的方法吗”这时候你光写出两种解法还不够得能说清两者的差别和取舍。4.1 时间/空间复杂度与实现风险对比直接上表格维度三指针迭代递归回溯时间复杂度O(n)O(n)空间复杂度O(1)O(n)递归栈代码量稍长约 12 行极短约 8 行理解难度直观需要理清三指针抽象但掌握模板很爽主要风险丢指针、边界少处理栈溢出、空指针适用场景工程实现、超长链表面试讲解、较短链表为什么迭代空间 O(1) 而递归空间 O(n)递归 N 层就要压 N 个栈帧栈帧数量与链表长度线性相关迭代只用额外prev、cur、next三个引用变量跟链表长度无关。数据规模在几百几千时差异不明显但如果链表有几万个节点递归很可能直接触发栈溢出这在工程上很致命。时间上两者都是 O(n)每个节点都被访问一次、修改一次谁也不会比谁快出量级差别。所以真正的分水岭是空间。4.2 面试官追问“你能优化吗”的应答思路如果你面试先写了递归版面试官问“能优化空间吗”你直接把三指针迭代版写出来说明递归开销在栈深度迭代只用常数空间就行如果你先写迭代版对方可能会问“能不能用递归更简洁地表达”你可以写出短小的递归版但一定要补一句递归版本在极端长链表下会有栈溢出风险合理取舍要结合数据规模。这段话最能体现一个工程师对代码的全面理解。还有一个常见追问“如果链表有环怎么办”这个问题其实已经超出反转本身了。反转有环链表会造成死循环正确做法是先检测环快慢指针再反转或者题目明确规定无环。你只要能说明“我会先做环检测或者在题目保证无环的前提下使用这个解法”就行。4.3 生产环境里我会选哪一版为什么真实项目里如果非要手写链表反转我会选三指针迭代版。原因很朴素第一栈空间不可控。服务器端处理的数据量可能很大递归深度一旦上万轻则栈溢出重则拖垮进程第二迭代版的所有状态都在局部变量里调试时加一个打印语句或者断点逐轮看prev、cur、next的变化非常直观第三迭代版几乎零额外依赖谁都能看懂。递归版在代码长度上占优但一句head.next.next head就够让维护者脑补半天如果不是在面试场景可读性反而是负分。当然如果语言本身对尾递归优化很好或者链表长度在可控范围比如几百以内递归版也可以作为首选——但前提是你的团队都熟悉这种写法。代码不是越短越好而是要在正确性和可维护性之间取平衡。5. 一次到位边界测试与四个高频变体练熟后反转类题通吃普通反转会写了但面试往往不会停在原题。下面这几个变体才是真正拉开差距的地方。我把边界测试和变体串在一起讲因为它们的核心都指向同一件事链表头尾变化时怎么保证连接不丢。5.1 边界测试用例清单不管迭代还是递归以下用例必须一遍过用例输入期望输出空链表nullnull单节点1 - null1 - null双节点1 - 2 - null2 - 1 - null奇数长度1 - 2 - 3 - 4 - 55 - 4 - 3 - 2 - 1偶数长度1 - 2 - 3 - 44 - 3 - 2 - 1空链表和单节点是递归基也是迭代版不用改一行就能直接工作的证明双节点检查你是否漏掉最后一个长一点的三节点或五节点能看出中间指针是否理顺。写一个辅助函数把链表打印出来把这几个用例跑一遍比任何纸上推演都来得快。5.2 变体一反转链表的前 K 个节点题目变成给一个链表和整数 k反转前 k 个节点第 k1 个节点之后的顺序不变。比如1-2-3-4-5k3结果应该是3-2-1-4-5。这个变体最有价值的点在于它要求你在普通反转的基础上额外管理“反转部分”和“未反转部分”的衔接。做法很简单把反转逻辑抽成一个辅助函数reverseKHead(head, k)内部就是用三指针迭代法循环执行 k 次而不是一直执行到链表末尾。循环结束后prev是反转后这 k 个节点的新头cur是原链表中第 k1 个节点的引用head作为这 k 个节点的原头在反转后变成了这一段的尾巴。所以最后执行head.next cur把这一段的尾巴接到后面剩余链表上再返回prev作为新头。public ListNode reverseKHead(ListNode head, int k) { ListNode prev null; ListNode cur head; for (int i 0; i k; i) { ListNode next cur.next; cur.next prev; prev cur; cur next; } head.next cur; // 把反转后的段尾接到剩余链表 return prev; }这个思路是后面区间反转和 K 个一组反转的地基一定要把reverseKHead这个辅助函数独立出来后面会反复用。5.3 变体二反转区间 [m, n]哑节点的引入时机如果题目改成反转链表中第 m 到第 n 个节点其中 m、n 从 1 开始计数其它部分保持原序怎么办最麻烦的情况是 m1因为此时反转后的新头会变成原链表第 n 个节点你需要直接返回新头。为了避免对边界做一大堆 if 判断我们引入一个哑节点dummy让dummy.next head。从dummy位置开始找第 m-1 个节点pre让pre永远指向反转区间的前驱。之后从pre.next开始反转 n-m1 个节点反转结束后pre.next指向反转后的新头原区间起点start反转前是pre.next变成反转后的尾巴让它指向cur也就是原第 n1 个节点。最终返回dummy.next。为什么哑节点是好设计因为它把“头节点也可能被替换”这件事变成统一逻辑不管反转区间从哪里开始pre都明确存在不会出现空指针。这在工程里是个通用技巧——凡是头节点可能变化的链表操作加一个哑节点代码瞬间好写一半。public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 1; i m; i) { pre pre.next; } ListNode start pre.next; ListNode cur start; ListNode prev null; for (int i 0; i n - m 1; i) { ListNode next cur.next; cur.next prev; prev cur; cur next; } pre.next prev; start.next cur; return dummy.next; }这段代码完整可跑m 和 n 都要在合法范围内。你可以试着把 m1、n链表长度 代入它会退化成整表反转逻辑完全兼容。5.4 变体三K 个一组反转如何在组内复用迭代逻辑把链表按 k 个节点一组反转最后一组不足 k 个时不反转。比如1-2-3-4-5k2结果是2-1-4-3-5。这个变体是面试高频也很适合展示对递归的运用每一组内部用reverseKHead反转组与组之间用递归衔接。递归版思路先用一个临时指针cur从head往后数 k 个节点。如果还没数够 k 个就到链表尾部了说明剩余不足 k直接返回head保持原序。如果数够了cur此时就是第 k1 个节点也就是下一组的起点。对当前这一组调用reverseKHead(head, k)得到反转后的组头newHead。此时head已经变成这一组的尾巴我们把它接到下一组的反转结果上head.next reverseKGroup(cur, k)。最后返回newHead。public ListNode reverseKGroup(ListNode head, int k) { ListNode cur head; int count 0; while (cur ! null count k) { cur cur.next; count; } if (count k) { return head; } ListNode newHead reverseKHead(head, k); head.next reverseKGroup(cur, k); return newHead; }这段递归跟反转链表的递归在结构上一模一样区别只是递归基不同前者的基是“当前链表长度为 1 或 0”这里的基是“剩余节点不足 k 个”。递归的威力就在这——它帮你把“处理完当前组”和“继续处理剩下组”之间的关系理清了。5.5 变体四两两交换相邻节点当作 K2 的特例两两交换可以看作 K 个一组反转在 k2 时的特殊形态1-2-3-4变成2-1-4-3。你完全可以直接调用reverseKGroup(head, 2)但如果面试官想考察你能不能写得再短一点可以记住这个递归写法。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; }每一步都在做一件事先把当前的两个节点连好再递归处理后面的链表。它和普通反转链表递归在结构上极其相似区别只是普通反转递归做的是 1 对 1 的反向连接这里是两两一组的反向连接。会了前者后者其实一秒就能推出来。最后分享一下我自己的练习习惯。每次复习链表反转我都不会只写一遍答案而是强制自己在一个晚上把普通反转、前 K 个反转、区间反转、K 个一组反转全部用迭代和递归各写一遍写完再打开调试器给定一个五节点链表一轮一轮看prev、cur、next的变化。这样做的收获不是背会了多少模板而是真正建立了对指针、引用、断链这些概念的直觉。等你在实际项目里遇到类似的链表操作你会发现大脑会自动浮现出prev和cur的画面bug 往往还没跑就提前被自己的心智模型拦住了。如果你也在准备算法面试我建议你别停留在“能过测试用例”这个层面多问自己一句如果这里改成递归空间复杂度会不会让我翻车如果链表有环我这段代码会卡多久多问几个为什么反转链表这道题才真正变成了你自己的东西。