刚刷题群里有朋友问我LeetCode 103 反转链表 II 这题怎么解其实光这个说法本身就藏着新手最常见的一个坑——LeetCode 上编号 103 的题目是二叉树的锯齿形层序遍历而真正叫“反转链表 II”的是第 92 题标题里的 103 大概率是题号记串了。不过没关系今天我就把“反转链表 II”当成主角从题号澄清、题目拆解、两种完整解法、边界 bug 到高频变体一条龙讲透。不管你是刚开始刷链表的小白还是准备面试想把模板练成肌肉记忆的选手这篇都能直接用。1. 题号澄清103 和 92 到底谁是谁1.1 两道题的正确打开方式先花点时间把题号说清楚不然照着错误题目刷半天心态很容易崩。LeetCode 官方编号里103 题是Binary Tree Zigzag Level Order Traversal中文通常叫二叉树的锯齿形层序遍历输入是一棵二叉树要求按层从左到右、再从右到左、再从左到右这样交替输出节点值。而Reverse Linked List II也就是反转链表 II是第 92 题给你一个单链表和两个整数 left、right要求反转从 left 到 right 这一小段其余部分保持不变。两道题放在一起对比其实非常清晰项目LeetCode 103LeetCode 92英文名Binary Tree Zigzag Level Order TraversalReverse Linked List II中文名二叉树的锯齿形层序遍历反转链表 II数据结构二叉树单链表核心操作BFS 逐层遍历并交替方向局部链表反转常见标签树、广度优先搜索链表、双指针为什么容易记混我猜有几个原因一是不少刷题榜单里这两道题挨得很近每次一截图就容易被一起记住二是有部分野鸡题单和旧版翻译把编号顺序搞乱过103 在某些地方被错标成“反转链表”三是纯数字本身没有语义刷题刷多了题号和内容经常会串。这里给大家一个建议以后找题时用“英文名 题号”双重定位比如直接搜 Reverse Linked List II – 92能避免很多低级乌龙。1.2 如果你真正想刷的其实是 103为了不让你走错片场我这里先花一小段把 103 的解法轮廓讲清楚本文后面第六节还会给出完整代码。二叉树的锯齿形层序遍历核心就是广度优先搜索BFS按层把节点塞进队列同时维护一个方向标志 leftToRight。奇数层用尾插法把节点值放进当前层结果偶数层用头插法把节点值倒着放进去。也可以直接用双端队列每次根据方向决定从队尾还是队头插入。这样完成的复杂度是时间 O(N)、空间 O(N)N 是节点总数。如果你确认自己要做的是 103那直接跳到第六节看代码就行如果你的目标是反转链表 II那请继续往下看接下来咱们把 92 题彻底吃透。2. 反转链表 II 的题目拆解与方案选型2.1 读懂题意比写代码重要先看题目给出的典型例子链表是 1 - 2 - 3 - 4 - 5left 2right 4要求反转第 2 个节点到第 4 个节点得到 1 - 4 - 3 - 2 - 5。还有个基础用例是链表只有一个节点 5left 1right 1输出还是 5因为只有一个节点反转了个寂寞。这个题难就难在它不是让你反转整条链表而是只反转中间一小段反转之后两头还要跟原有的链表完美接上。很多人一上来就写反转链表的经典循环结果反转完发现前半段和后半段全部断开了。我习惯把问题拆成三件事第一找到 left 位置节点的前一个节点记作 pre它是连接前半段和反转后新区间的关键。第二把 left 到 right 这段内部的 next 指向全部反过来也就是区间内部的链表方向翻转。第三把反转后的区间头尾分别和 pre 以及原 right 后面的节点接回去。如果你把这三个问题分开想就会发现“反转区间内部”反而是最机械的一步真正容易出错的是边界连接。为了统一处理 left 1 这种没有前驱节点的场景业界标准做法是引入一个虚拟头节点 dummy让 pre 永远存在。很多第一次做这题的人不理解为什么非要加 dummy等到 left 1 时你才会发现没有 dummy 的话 pre 根本无从说起代码里全是 if-else 特判又丑又容易错。2.2 三种主流解法的取舍看到这道题网上能搜到的解法大致可以分成三类解法核心思路时间复杂度空间复杂度适合场景头插法穿针引线一次遍历每轮把 cur 的下一个节点摘下来插入到 pre 后面O(N)O(1)面试首选原地操作截取区间再反转切出 left 到 right 这段先反转再接回原链表O(N)O(N)初学者便于理解但边界指针多递归法递归下沉到区间起点反转前 N 个节点O(N)O(N)练习递归思想代码简洁我自己的建议是如果你在准备面试优先掌握头插法因为它一次遍历、常数空间面试官听了会点头而且代码固定写错概率低如果你想透彻理解链表操作可以再用截取法练一遍帮你建立“四个边界指针”的直觉递归法属于锦上添花适合你第二遍、第三遍刷题时用来巩固递归思路。接下来两节我把最推荐的头插法和很有意思的递归法都完整拆给你看。3. 方法一一次遍历头插法面试推荐3.1 头插法为什么能边遍历边反转头插法的核心就一句话每次把当前指针 cur 后面的那一个节点摘下来插入到 pre 的后面。这个过程重复 right - left 次通道走完区间自然反转。我拿例子走一遍。初始链表 dummy - 1 - 2 - 3 - 4 - 5left 2right 4。第一步pre 指向 1cur 指向 2。接下来要反转的是 2、3、4 三个节点所以循环 right - left 2 次。第一轮把 cur 的下一个节点也就是 3摘出来插入到 pre 的后面。链表变成 dummy - 1 - 3 - 2 - 4 - 5。这时候你会发现2 被挤到后面去了但 cur 仍然指向 2它已经变成区间内部的尾部节点。第二轮把 cur 现在的下一个节点 4 摘出来再插入到 pre 的后面。链表变成 dummy - 1 - 4 - 3 - 2 - 5。这时候 4、3、2 的顺序已经反转完成循环结束直接返回 dummy.next。为什么要循环 right - left 次因为区间内一共有 right - left 1 个节点第一个节点 cur 已经在正确位置反转后区间末尾每次只处理一个被摘下来的节点处理 right - left 次后剩余节点全部完成转移。3.2 完整代码与逐行解释这里给出 Java 实现写法非常常规适合直接背下来当模板class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 虚拟头节点统一处理 left 1 的情况 ListNode dummy new ListNode(0); dummy.next head; // pre 走到 left 的前一个节点 ListNode pre dummy; for (int i 0; i left - 1; i) { pre pre.next; } // cur 指向区间第一个节点它最终会成为区间末尾 ListNode cur pre.next; // 核心循环执行 right - left 次 for (int i 0; i right - left; i) { ListNode next cur.next; // 1. 取出要移动的节点 cur.next next.next; // 2. 让 cur 跳过这个节点 next.next pre.next; // 3. 把取出的节点指向 pre 后面的节点 pre.next next; // 4. 把 pre 指向取出的节点 } return dummy.next; } }这段代码最核心的只有循环里的四行每行都有它存在的道理。第一步先用 next 把 cur.next 存下来因为下一步马上就要改 cur.next不提前存的话节点就找不到了。第二步让 cur 越过 next相当于把 next 从链表中摘掉此时 cur 仍然指向链表原位置的下一个节点。第三步是头插的关键让 next.next 指向 pre.next因为 pre 在循环过程中会不断改变指向所以这里不能用别的变量代替 pre.next。第四步把 pre.next 更新为 next让新节点真正落到 pre 后面。这四个步骤的顺序绝对不能乱第三步和第四步如果颠倒pre.next 提前变了后面就拿不到正确的旧值了。3.3 一个容易忽略的细节头插法里有很多人搞不懂为什么 cur 指针从头到尾都不用移动因为你每次都是把 cur.next 这个节点拿走去头插而 cur 一直是区间里原来的第一个节点。随着一轮一轮执行cur 这个节点会被后面的新节点不断挤到更靠后的位置最后自动成为反转后区间的末尾完全不需要手动移动它。这也是这个算法最优雅的地方。为了加深印象我用表格把状态变化列出来以 dummy - 1 - 2 - 3 - 4 - 5left 2right 4 为例操作轮次precurnext链表状态初始123dummy - 1 - 2 - 3 - 4 - 5第一轮123dummy - 1 - 3 - 2 - 4 - 5第二轮124dummy - 1 - 4 - 3 - 2 - 5看到没有cur 从头到尾都是 2但链表中 2 的位置被越挤越靠后。这个细节理解了头插法基本就通了。4. 方法二递归实现区间反转4.1 先学会反转前 N 个节点递归法的地基是“反转链表前 N 个节点”你可以把它理解成反转整个链表的一个特例。经典递归写法里需要一个全局变量 successor用来记录反转完成后原第 N 个节点的下一个节点是谁因为反转后这部分要能接回去。class Solution { // 记录反转前 N 个节点后的后继节点 private ListNode successor null; // 反转以 head 为起点的前 n 个节点返回新的头节点 private ListNode reverseN(ListNode head, int n) { if (n 1) { // 记录第 n 个节点的下一个节点 successor head.next; return head; } // 递归反转后续节点newHead 是反转后的新头 ListNode newHead reverseN(head.next, n - 1); // 让当前节点的后继的后继指向自己 head.next.next head; // 当前节点的后继指向 successor避免成环 head.next successor; return newHead; } }这个递归过程你只要关注两点。第一base case 是 n 1此时走到第 n 个节点先把它的下一个节点存到 successor然后返回自己因为前 N 个节点反转之后第 N 个节点就是新头。第二回溯阶段每一层都在做一件事把原来的 next 指回自己再把自己指向 successor。最终整段链表的 next 方向全部调转并且末尾正确接上原来的后继。4.2 把区间问题递归化有了 reverseN区间反转就很好写了。核心思想很简单如果 left 1那问题直接变成反转以 head 为起点的前 right 个节点调用 reverseN(head, right) 就能解决如果 left 1那么 head 不需要动只需要递归处理 head.next同时把 left 和 right 都减一。每递归一层问题的起点就往后挪一个节点直到起点恰好是 left 位置。class Solution { private ListNode successor null; public ListNode reverseBetween(ListNode head, int left, int right) { // base case起点就是第一个节点退化为反转前 right 个节点 if (left 1) { return reverseN(head, right); } // 递归处理后续链表区间整体向后平移一位 head.next reverseBetween(head.next, left - 1, right - 1); return head; } private ListNode reverseN(ListNode head, int n) { if (n 1) { successor head.next; return head; } ListNode newHead reverseN(head.next, n - 1); head.next.next head; head.next successor; return newHead; } }用之前的例子 1 - 2 - 3 - 4 - 5left 2right 4 走一遍。第一次进入 reverseBetweenleft 2不减到 1所以递归处理 2 - 3 - 4 - 5left 变成 1right 变成 3。这时候 base case 触发对以 2 为头的前 3 个节点调用 reverseN把 2 - 3 - 4 反转成 4 - 3 - 2。回到第一层得到 head.next 4 - 3 - 2 - 5而节点 1 的 next 指向这个新头所以最终结果是 1 - 4 - 3 - 2 - 5。整个过程非常巧妙代码也相当短。4.3 两种写法怎么选如果是在面试现场我个人的选择永远是头插法。原因很实际递归代码虽然漂亮但需要向面试官解释 successor 的作用、递归的压栈过程稍微说漏一句就容易显得理解不透。而且递归的空间复杂度是 O(N)在链表很长时不如迭代稳定。不过递归法在训练思维的阶段价值很大它能让你对“链表问题天然适合递归”有更深的体感。建议刷题顺序是先头插法写到滚瓜烂熟再用递归法作为进阶练习。5. 高频边界条件与调试心得5.1 常见翻车点 Top 5这题我前前后后刷过很多遍也在白板上被面试官刁难过。下面这些坑几乎所有人都踩过整理成一张速查表写代码前先扫一眼问题场景典型症状排查方向left 1 时没有统一处理返回结果丢掉了原始头节点输出从第 2 个节点开始检查是否用了 dummy 虚拟头节点left right区间只有一个节点代码却把指针改了循环 right - left 次次数为 0 时不应有任何指针变动循环里第三、四步顺序写反链表直接出现环打印时死循环牢记先把 next.next pre.next再更新 pre.next区间反转完没有接回 pre前半段和反转区间断开反转结束后检查 pre.next 是否指向新区间头部right 超过链表实际长度出现空指针异常题目通常保证约束但要养成防御性编程习惯其中 dummy 节点是最核心的。没有 dummy当 left 1 时你就要写 if 特判而且返回值到底是 head 还是新区间头一定要反复确认很容易乱。有了 dummy不管 left 是多少pre 一定存在最后统一返回 dummy.next代码逻辑完全一致。5.2 白板快速写对的小套路我发现刷链表题有个非常实用的方法论永远先画图再写代码最后用具体例子走一遍。哪怕是在面试白板上你画一个 1 - 2 - 3 - 4 - 5 的例子标出 pre、cur、next 的变化写代码的效率会比直接开写高出一大截。写完以后推荐用这组用例自测链表 1 - 2left 1right 2预期结果 2 - 1。链表 1 - 2 - 3left 2right 3预期结果 1 - 3 - 2。链表 1 - 2 - 3 - 4 - 5left 1right 5预期结果 5 - 4 - 3 - 2 - 1。链表 5left 1right 1预期结果 5。这四组用例分别覆盖了区间在头部、区间在尾部、区间覆盖整条链表、单节点链表四种典型边界。多跑几遍正确性会扎实很多。另外分享一个调试技巧写一个打印链表的辅助函数把链表转成字符串然后在头插法的循环每一轮末尾都打印一次链表状态。比如用 Java 的话可以在循环里拼 StringBuilder看每一步的中间结果。这个技巧在做复杂链表题时几乎能省掉一半推理时间。6. 举一反三从 92 题延伸到高频变体6.1 反转整个链表其实是区间反转的特例很多人刷到 LeetCode 206 反转链表时会另写一套逻辑其实没必要。只要你把区间设置为 left 1right 链表长度92 题的代码就自动变成了反转整个链表。你可以把 206 理解为 92 的 full range 版本也可以把 92 理解为“局部区间版的 206”。掌握头插法之后206 的常规迭代解法你可以直接通过“把 pre 固定在 dummy循环 n - 1 次”推导出来复用到极致。6.2 从 92 到 25k 个一组翻转链表LeetCode 25 是 k 个一组翻转链表它看起来比 92 难不少但本质上是区间反转的循环版本。做法是每 k 个节点作为一组组内调用一次反转逻辑然后处理好组间连接。你可以复用 92 题里的头插法模板每轮反转前先让 pre 走到当前组的头节点前一个位置再执行 k - 1 次头插反转完一组后更新 pre 到新的组前驱继续下一组。用伪代码表示就是dummy - 链表头 pre dummy while 剩余节点数 k: 定位一组 k 个节点 对组内执行 k-1 次头插 pre 移动到这一组反转后的末尾这样一看25 题其实约等于“把 92 题的区间反转重复执行多次”。链表题就是这样看似题型很多底层模板就那么几个你吃透一个就能串起一片。6.3 顺带把 103 的真实解法写出来既然开头提到了题号混淆最后还是把 LeetCode 103 的完整解法放出来免得你想刷 103 还要再翻一篇文章。下面这段 Java 代码用 BFS 按层遍历借助 LinkedList 的头插和尾插来切换方向简洁且容易记class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean leftToRight true; while (!queue.isEmpty()) { int size queue.size(); LinkedListInteger level new LinkedList(); for (int i 0; i size; i) { TreeNode node queue.poll(); if (leftToRight) { level.addLast(node.val); } else { level.addFirst(node.val); } if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } leftToRight !leftToRight; result.add(level); } return result; } }思路非常简单每次从队列里取出当前层全部节点根据方向决定往 level 列表的尾部还是头部插入。方向每层翻转一次。因为 LinkedList 的头插是 O(1)所以整体效率很高。刷到这题的同学直接用这个版本就够了。7. 链表题的刷题经验与最终记忆方法7.1 链表题的通用复习法我见过不少人刷链表题每道题都是独立记一种写法今天 206 背一套明天 92 背一套后天 25 又背一套结果没过多久全忘光。链表题的正确打开方式是先找出底层共性。反转类题目的共同模板就是“虚拟头节点 前驱指针 待处理指针”所有反转花样都能收敛到这个模型里。所以我的复习策略是以 92 题为锚点把 206、25、24 两两交换节点这些题都拿出来对比着刷看它们对这个模板做了哪些小改动。7.2 我踩过的坑和最终记忆方法最后分享一个我自己的黑历史。第一次刷 92 时我自认为思路清晰直接在 IDE 里开写没有加 dummy结果 left 1 的测试用例跑出来少了整个头节点排错排了十几分钟才发现是 pre 初始化的问题。后来我把所有链表反转题都统一成一套逻辑再没翻过车。这套逻辑可以浓缩成一句记忆口诀dummy 固定起点pre 走到 left 前面循环 right - left 次摘 cur.next 插到 pre 后面。每次写这道题我脑子里自动浮现这句口诀代码就直接敲出来了。你也试试把每道链表题都总结成一句话学习效率会高很多。再补一个小技巧如果担心边界没有覆盖全可以自己写一个由 int 数组生成链表的辅助方法再把结果转回数组做断言。这个方法在本地调试时特别好用能一眼看出链表有没有断、有没有环、反转是否准确。搞定了这些92 这道题对你来说基本上就只剩下“熟练度”的问题了。