最早开始刷题那段时间反转链表是我反复写了无数遍的一道题。LeetCode热题100里的链表题不少但这道反转链表几乎可以算链表的题眼——它能把迭代、递归、指针操作、边界处理一次讲清楚。写这篇文章是因为我发现太多人不是不懂思路而是一拿起笔就处理不好指针指向或者递归函数返回值为什么要那样写搞不明白。这篇不只是给答案我尽量把从画图推导到代码落地的全过程都讲透看完以后不只是会做这一道题后续碰到的链表类题目也能有一个可以依托的思考框架。1. 为什么反转链表值得反复练题目价值与常见误区1.1 链表操作的核心考察点链表和数组最大的区别在于数组可以通过下标直接访问任意元素而链表只能从头部开始沿着 next 指针一个个走。反过来说链表的优势是插入和删除不需要搬动其他元素只要改变指针指向就可以。反转链表这个操作本质上是把方向反过来它考察的是你对节点引用关系的敏感度。很多人会问这道题看起来这么简单为什么能进热题100我的理解是它虽然代码量很少却同时覆盖了几个高频考点指针变量的保存与覆盖顺序遍历过程中对链表的断链处理递归思路里如何把一个大问题分解成小一号的问题边界条件空链表、单节点链表的处理习惯这些能力恰好是后续解决复杂链表题的基础。比如反转链表II反转区间、K个一组翻转链表、回文链表等题目几乎都是在这道题的基础上加条件变体。所以把这道题吃透收益不是一道题而是一类题。1.2 最常见的三个误区我见过不少人在写这道题时掉进同样的坑里这里先拎出来说后文会再详细展开。误区一试图用数组或栈保存链表节点再反向重建。这种解法虽然能过测试用例但完全回避了链表指针操作面试时如果只写出这种答案基本等于告诉你对链表不熟。刷这道题的目的就是练指针不是练数据结构转换。误区二迭代时先改当前节点的 next却没有提前保存原来的后继导致链表后半段丢失。这是典型的断链问题后面我会用详细图示讲清楚为什么必须先保存再修改。误区三递归解法里搞混递归函数的返回值。递归解法返回的不是反转后的当前子链表的头节点而是反转后的整个链表的头节点——也就是原链表的最后一个节点。这个值在内层递归返回后必须原封不动地继续向上传递中间任何一层都不能把它改掉。先记住这三点下面我们分别用迭代和递归两条路线把每个细节掰开来看。2. 迭代解法三指针的核心逻辑推导2.1 先用画图看懂指针走位迭代解法通常叫三指针法用到的三个指针是 prev、curr、nextTemp。很多人上来就把三个指针怎么赋值背下来但没理解为什么是这三个一旦题目稍作变化就卡住。我的建议是先在纸上画一条链表给每个节点标上编号然后把每一步指针变化画出来。初始状态是这样的prev 指向 null因为新链表的头节点的 next 最终要指向 nullcurr 指向链表头节点nextTemp 用来临时保存 curr.next防止修改 curr.next 之后找不到原来的后继每轮循环做的事情本质上只有两步让当前节点的 next 指向前一个节点这就是反转方向三个指针整体向右移动一位处理下一个节点画图时你会发现一个关键点修改 curr.next 之前必须先让 nextTemp 把原来的后继接住。如果先执行 curr.next prevcurr 原来的下一个节点就找不到了整个链表从第二个节点开始就被你亲手弄丢了。这也是我前面说的断链问题。用生活化的比喻来理解三指针就像排队反转方向时你既要拉住前面已经转好方向的人又要拽住后面还没转的人腾出的那只手才能去调整当前人的朝向。顺序一错后面的人就跟丢了。2.2 Java代码实现与逐行解释迭代解法的 Java 代码非常简洁public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextTemp curr.next; // 先保存后继节点 curr.next prev; // 反转指针方向 prev curr; // prev 前移 curr nextTemp; // curr 前移 } return prev; }逐行看ListNode prev null;初始化前驱节点。反转完成后原来的头节点会变成新链表的尾节点它的 next 必须指向 null所以 prev 从 null 开始。ListNode curr head;当前节点从原链表头部开始遍历。while (curr ! null)循环终止条件是当前节点为 null。当 curr 走到链表末尾的下一个位置时说明所有节点都已经处理完。ListNode nextTemp curr.next;先记下当前节点的下一个节点防止下一步改变指针后无法继续遍历。这一步是所有断链问题解法的核心。curr.next prev;把当前节点的 next 指向前一个节点完成一次反向。prev curr;prev 前进到当前节点下一轮循环中它就是前一个节点。curr nextTemp;curr 前进到原来保存的后继节点继续处理。return prev;循环结束时 prev 正好指向原链表的最后一个节点也就是新链表的头节点。有一点值得注意循环结束后 nextTemp 变量存在与否已经无所谓了它只是循环体内的临时变量。真正决定结果的是 prev所以返回值是 prev 而不是 currcurr 这时候已经是 null。2.3 边界情况的验证写代码不能只看主流程边界条件是最容易出低级错误的地方。我习惯在写完代码后立刻自测三个场景空链表head 为 null。这时 while 循环一次都不进入直接返回 prev也就是 null。结果符合预期空链表反转后还是空链表。单节点链表head 只有一个节点。第一轮循环中nextTemp 为 null然后 curr.next 指向 nullprev 指向这个节点curr 变成 null循环退出。返回 prev也就是原唯一的节点本身它的 next 已经是 null。结果符合预期。多节点链表比如 1 - 2 - 3三轮循环后prev 从 null 逐步变成 1、2、3最终返回 3且 3 的 next 指向 22 的 next 指向 11 的 next 指向 null。验证通过。这三个场景代码里甚至有天然防御空链表和单节点链表都不用额外加 if 判断因为 while 条件本身就能处理。这也是我喜欢迭代法的原因之一逻辑干净边界少。3. 递归解法从反转整个链表到反转一个节点3.1 递归的递推关系怎么找递归解法的难点不在于代码本身而在于你能不能找到那个递推关系。很多人学递归的时候喜欢在脑子里一层层展开函数调用试图手动模拟完整调用栈结果没几步就晕了。我的经验是不要试图从头到尾跟踪整个递归过程你要做的是信任递归只关心两件事——递归函数的功能是什么以及在最小规模问题时它的答案是什么。对于反转链表来说我们定义递归函数reverseList(head)表示将以 head 为头节点的链表反转并返回反转后的新头节点。现在假设head是当前节点它后面那条子链是head.next。我们不去想整条链怎么反转只考虑一件事如果head.next开头的那一段链表已经反转好了我该做什么举例来说链表是 1 - 2 - 3 - 4 - 5。进入递归后head是节点1而调用reverseList(head.next)会得到反转后的子链表 5 - 4 - 3 - 2返回值是原链表最后一个节点5。此时的状态是节点2 变成了子链表的尾节点而节点1 还孤零零地待在前面它的 next 仍然是节点2。我们要做的就是让节点2 的 next 指向节点1然后节点1 的 next 指向 null。这样整条链表就成为 5 - 4 - 3 - 2 - 1。这段逻辑落实成代码只有两行head.next.next head; head.next null;第一行的含义是当前节点下一个节点的 next指向当前节点相当于把箭头掉转方向。第二行的含义是当前节点变成新链表的尾节点所以它的 next 必须是 null。递归的终止条件也决定了它的基础如果head为 null或者head.next为 null也就是当前节点自己就是最后一个节点直接返回head。因为只有一个节点或者没有节点时根本不需要反转返回本身即可。3.2 代码细节为什么返回newHead完整的递归代码如下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; }这里最容易被误解的就是newHead。很多初学者以为递归返回的应该是当前这层处理完之后的头节点于是写return head;结果整条链表反转之后只剩最后一个节点前边的节点全丢了。实际上newHead在整个递归过程中始终指向的是原链表的最后一个节点它在最内层递归递归到底的那一层被确定下来然后一层一层原封不动地向上传递。每次外层递归只需要做两件事调整当前层局部两个节点的指向关系head.next.next head;和head.next null;把已经确定好的newHead继续往上传打个比方这就像你在队伍队尾喊了一声我是最后一个前面的人跟着我反向排然后这句话newHead一路传回队首队首最终拿到了新队头是谁。中间每层都在调整自己和下一个人的相对位置但那个新队头的身份一直没变。3.3 递归的隐患与适用场景递归解法虽然代码比迭代法更短逻辑也更优雅但它有很现实的成本调用栈深度。当链表很长比如几万个节点时递归会无限地压栈最终可能抛出栈溢出异常。Java 里递归深度受默认栈大小限制一般几千层到一万层左右就危险了。迭代法只用常数级额外空间完全不受这个限制。所以我的建议是面试时如果明确问了能不能用迭代实现优先写迭代。如果面试官想看你对递归的理解可以用递归展示思路但最好主动提一句递归空间复杂度是 O(n)在链表很长时可能有栈溢出风险。在实际生产代码中处理链表优先选择迭代方案。另外还有一个常见问题递归解法里的head.next null是做什么的如果不写会出现什么情况我试过故意删掉这行代码结果发生了非常典型的环形链表问题。原链表尾节点的 next 本来指向 null但如果中途某个节点没有把 next 置空反转后的最后一个节点可能仍然指向之前的节点形成环。举例来说1 - 2 - 3反转后应该是 3 - 2 - 11 的 next 必须是 null。如果 1 的 next 仍然是 2那么从 1 开始又能回到 2链表就变成循环了。所以这一行不是可有可无的它是确保新链表正常终止的关键。4. 两种解法横评复杂度、面试风格与选择思路4.1 时间与空间复杂度对比把两种方案放在一起对比我们对这道题的时间复杂度其实没有争议都是 O(n)因为不管用迭代还是递归每个节点都只被访问了一次。真正的区别在于空间复杂度。方案时间复杂度空间复杂度核心特点迭代法O(n)O(1)三个指针常数空间无栈溢出风险递归法O(n)O(n)代码简洁思路优雅但需要调用栈空间这里说递归空间复杂度 O(n)指的是递归调用本身消耗的调用栈。即使递归函数内部没有额外的局部数组或容器每一层递归调用都会占用栈帧空间链表多长栈就多深。这个成本是隐性的表面看不到却真实存在。时间复杂度上还有一个容易被忽略的小细节两种解法虽然都是 O(n)但迭代法在遍历时每个节点只做一次指针赋值常数很小递归法除了每层做指针赋值还要承担函数调用的开销。在数据量不大时差距可以忽略但如果追求极致性能迭代法通常更有优势。4.2 面试时怎么选面试场景和刷题场景不完全一样。刷题时你只需要让代码通过测试面试时你需要同时展示思路的广度和代码的稳健性。我的经验是面试中遇到反转链表可以这样组织回答先说思路这道题有迭代和递归两种主流解法。先写迭代因为它直观、稳定、空间复杂度低面试官不会有任何质疑。如果面试官追问还有别的方法吗再把递归方案写出来并且主动解释递归的终止条件和返回值设计。最后对比两者的空间复杂度主动提一句递归在极端情况下的栈溢出隐患。这个顺序的好处是先给出最稳的答案再展示更全面的理解。千万不要一上来就写递归万一面试官追问递归细节自己反而讲不清楚就很尴尬。反过来如果题目明确说用递归实现那就老老实实写递归并把递推关系讲明白。4.3 一点微优化迭代解法本身已经是最优的 O(n) 时间和 O(1) 空间但实际操作中有几个小技巧可以让代码更稳给方法加上入参校验并不必要因为空链表在 while 条件下天然返回 null。显式加 if 判断反而画蛇添足。临时变量nextTemp的命名要清晰不要用t或temp这类语义不明的名字面试官看代码时读起来会吃力。方法返回前可以用断言或者测试用例验证结果刷题环境里直接跑样例即可本地练习时可以写一个辅助方法打印链表逐节点检查指向。还有一个我经常在本地练习用的技巧把链表节点定义和 toString 方法加上自测时可以直接打印1 - 2 - 3一眼看出反转结果是否正确。这个问题我在下一部分展开。5. 实测过程中的坑与调试技巧5.1 空指针与断链的典型症状反转链表代码量很少但报错信息却很有迷惑性。我把我自己踩过的坑和身边人问过的问题总结成几类典型症状方便你对号入座症状一运行时报 NullPointerException位置指向head.next.next head;这一行。这是递归解法最常见的问题。原因通常是递归终止条件写错了比如只写了if (head null)而没有写if (head.next null)。当递归到最后一个节点时head.next为 null继续调用reverseList(head.next)虽然能返回 null但执行head.next.next head时head.next是 null对 null 取 next 自然就崩了。症状二反转之后链表只剩最后一个节点前面的节点全部丢失。这是典型断链问题发生在迭代里没有先保存后继节点。比如你写了curr.next prev;之后才去找原来的下一个节点这时已经晚了。链表一旦断掉后面的节点跟着全丢。症状三反转之后出现循环链表打印链表时一直打印不完。这是递归里漏了head.next null;。反转后的尾节点仍然指着原来的下一个节点形成了一个环。测试用例如果只检查头节点值是否正确可能还发现不了这个问题但只要遍历一次链表就会陷入死循环。5.2 用打印法可视化检查我在本地练习时必做的操作是写一个打印链表的方法。节点定义和打印方法如下class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } Override public String toString() { StringBuilder sb new StringBuilder(); ListNode cur this; while (cur ! null) { sb.append(cur.val); if (cur.next ! null) { sb.append( - ); } cur cur.next; } return sb.toString(); } }有了这个 toString测试代码就可以这样写public static void main(String[] args) { ListNode head new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))); System.out.println(原链表: head); ListNode reversed reverseList(head); System.out.println(反转后: reversed); }输出是原链表: 1 - 2 - 3 - 4 - 5 反转后: 5 - 4 - 3 - 2 - 1打印法还有个好处它能在你写递归版本时帮助确认每一层调用后的状态。你可以在递归函数里临时加一行打印输出当前 head.val 和 head.next.val看到递归一层层往上走时指针的变化。排查完记得把打印行删掉。5.3 一些测试用例除了常规的多节点链表我每次写完这道题还会固定跑这几个用例// 空链表 ListNode empty null; ListNode res1 reverseList(empty); System.out.println(res1 null ? pass : fail); // 单节点链表 ListNode single new ListNode(42); ListNode res2 reverseList(single); System.out.println(res2.val 42 res2.next null ? pass : fail); // 两个节点 ListNode two new ListNode(1, new ListNode(2)); ListNode res3 reverseList(two); System.out.println(res3.val 2 res3.next.val 1 res3.next.next null ? pass : fail); // 正常多节点 ListNode multi new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4)))); ListNode res4 reverseList(multi); System.out.println(res4 ! null ? res4.toString().equals(4 - 3 - 2 - 1) ? pass : fail : fail);这些用例覆盖了空链表、单节点、双节点、多节点四类场景对于这道题来说已经足够。如果你还想更严谨可以增加反转后尾节点的 next 是 null这个检查这是很多测试用例没覆盖到的隐性要求。6. 从热题100出发反转链表的常见变体6.1 反转部分区间热题100里有一道反转链表II要求反转从第 left 到第 right 个节点之间的子链表其余部分保持原样。这道题看起来是新题实际上只是给反转链表加了一个区间限制。核心思路是先找到第 left-1 个节点作为前驱然后从第 left 个节点开始用迭代法的指针逻辑反转 length 个节点length right - left 1最后把反转好的子链表再接回原来的链表中。这个题目特别容易出问题的点是区间边界的拼接如果 left 是 1从头节点开始反转就没有前驱节点处理完需要直接更新头节点如果 left 大于 1需要把前驱节点的 next 指向反转后的子链表头节点同时把反转后的子链表尾节点接到原链表第 right1 个节点上。这些细节全部依赖你对基础反转链表指针操作的熟练度。6.2 每K个一组翻转K个一组翻转链表是反转链表系列里最难的一题。它要求每 K 个节点为一组进行反转最后一组节点数不足 K 则保持原样。解法思路仍然基于基本的反转链表函数只是多加了两层控制先统计链表长度确定可以完整分几组。每一组内部调用反转逻辑把小组的头尾都反转过来。把多个小组串联起来。这道题代码写起来比较长但对迭代法三指针的掌握要求极高。因为你不仅在每个小组内要循环反转还要跨小组维护 prev 和 next 的指向。我在写这道题时最大的感悟是反转链表都不熟练的话后面这些变体根本无从下手。所以热题100把反转链表放在中间偏前的位置是有道理的它是整个链表题型的地基。6.3 链表反转的通用思考框架把基础题、区间反转、K 个一组翻转放在一起看我发现它们背后有一个共同的框架总共分三步第一步找到要反转的区间。用 prev 标记区间前一个节点用 end 标记最后一个要反转的节点。第二步反转区间内的指针方向。不管区间多长核心操作都一样保存后继、反转 next、推进指针。第三步把反转后的局部链表重新接回原链表。注意维护区间前驱和后继的连接特别是当区间包含原链表头节点时头节点会变化。你可以拿这个框架去套后面遇到的所有链表翻转类问题会发现大部分解法都是这三步的变体。区别只在于区间怎么找反转后怎么接而怎么反转始终是那道最基础的反转链表。我个人在实际刷题中的体会是反转链表这种题看十遍不如手写一遍。建议你先别急着背代码按我说的方法在纸上画一条链表用箭头一步步画出迭代过程中三个指针的位置变化再对照着写代码。画一遍、写一遍、跑一遍测试用例这套流程走完后面遇到任何反转类的变体题你都会比那些只背答案的人从容得多。最后再分享一个小技巧如果你发现迭代和递归经常写混可以记住一句话——迭代法是边走边改递归法是先到底再回头改。这两种思维模式都不难关键是在正确的场景用正确的那个。