LeetCode 103锯齿遍历与92反转链表：边界控制与模板拆解

很多刷题的朋友看到“Leetcode 103 反转链表 II”这个标题第一反应多半是懵的LeetCode 103明明是二叉树的锯齿形层序遍历怎么跟反转链表扯到一起了其实这是典型的题号记混——反转链表系列里真正叫“反转链表 II”的是第 92 题而 103 题作为二叉树层序遍历的变种同样是面试里的高频考点。这篇文章就把这两个容易混淆的题目放在一起拆开讲既把 103 题的 BFS 层序变体讲透也顺手把 92 题反转链表 II 的两种主流解法迭代头插、递归按实操标准过一遍。之所以把这两题拼到一篇里是因为它们在思路上有一个共同的内核局部反转/局部变换时必须精确控制边界而且都很依赖“保护节点”或“层标记”来避免边界溢出。二叉树要按“左→右、右→左”交替收集每层节点链表要把第 m 到 n 个节点原地逆序两者都要求你在遍历过程中记住“上一层的终点”或“反转区间前驱”一旦忘记保留现场写出来的代码必然在边界用例上崩。这篇文章适合正在刷 LeetCode 热门 100 题、准备周赛或面试前突击链表/二叉树专题的读者我会从题目定位、展开思路、完整代码、坑点排查一路讲到底最后聊几句怎么把这些技巧平移到类似题目上。1. 项目概述两道题到底在考什么1.1 Leetcode 103 的准确身份锯齿形层序遍历LeetCode 103 原题叫Binary Tree Zigzag Level Order Traversal中文常译作“二叉树的锯齿形层序遍历”或“之字形遍历”。题目要求从根节点开始逐层从左往右、再从右往左交替输出节点值。换句话说第一层根所在层从左到右第二层从右到左第三层又从左到右如此往复。这道题在 LeetCode 热门 100 题里不算最靠前但它在面试中出现的频率非常高尤其是电商、地图导航这类需要“逐层扩散”的业务场景。面试官把 102 题普通层序遍历做一次小改动就成了 103 题。它考察的核心就两个层序遍历的 BFS 模板是否熟练以及能否用双端队列或倒序收集的方式处理“层内顺序反转”。只要 102 题写得顺手103 题只是多了一个“按层奇偶切换方向”的步骤。1.2 题号混淆背后的出题逻辑反转链表 II 真实编号为 92再说回“反转链表 II ”它的真实题号是 LeetCode 92考察的是单链表中“从第 m 个节点到第 n 个节点”这一段区间内的反转区间外的节点保持原顺序。这道题相比 LeetCode 206反转整个链表难度提升在于你必须在反转结束后正确地把区间头部接到前驱节点、把区间尾部接到后继节点。很多人 206 题倒背如流一写 92 就崩原因不外乎三个没加 dummy 节点导致头节点被反转时丢失入口没保存第 m-1 个节点作为“前驱锚点”反转过程中被 next 指针绕晕。把 103 和 92 放在一起看它们恰好覆盖了面试中两个高频基础数据结构二叉树和单链表。二叉树的层序变体考“队列 方向标记”链表的局部反转考“指针重连 边界锚点”。这两类模板吃透面试中至少能顶住一轮算法手写。1.3 热词背后的真实需求从题解到周赛的进阶闭环再结合“leetcode题解”“leetcode周赛430”“leetcode 073爱吃香蕉的狒狒”这些热词看现在的刷题人群早就不是“做完就扔”的状态了。特别是周赛 430 出现后很多人在讨论区求 103 这种“看似简单但边界极多”的题解说明中等难度题反而是刷题瓶颈简单题一遍过困难题直接放弃只有中等题最能暴露问题。“073 爱吃香蕉的狒狒”则是另一类二分查找题它和 103 没有直接关系但做题思路一致——把一个看起来要模拟的过程转化成对“答案区间”的二分逼近。我在后面第 5 节会专门讲怎么把这些看似散落的题串成知识网络。2. 核心细节解析为什么 BFS 是锯齿遍历的最优解2.1 三种可行方案对比BFS、DFS 逆序、双端队列面对 103 题初学者最容易想到的是“递归遍历按深度分层深度为偶数时正序输出奇数时逆序输出”。这在直觉上没错但实现时要用 DFS 配合一个二维数组每层先收集再统一反转。这种方案的时间复杂度同样是 O(n)但空间复杂度在最坏情况下退化为 O(n) 的递归栈而且代码分支较多容易把“当前在哪一层”搞混。另一个更直接的方案是用BFS 普通队列把每一层节点从左到右入队收集完成后判断当前层序号如果是奇数层从 0 层开始数就把这一层的列表反转再放入结果集。这个方案足够简单但每层都要做一次 reverse相当于多了一次线性扫描理论上总时间仍为 O(n)只是多了一个常数系数。第三种方案是BFS 双端队列Deque在收集当前层节点值时不先存列表再反转而是根据层号直接决定往队尾追加还是往队头插入。这样省去了反转步骤代码也更“工程化”。我倾向于用这种方式写因为它把“方向”这个变量直接做进了输出容器逻辑上更统一。2.2 手写 BFS 模板队列、层大小、方向标记三位一体BFS 层序遍历的经典模板是初始化队列放入根节点每次取出当前队列的全部节点这一层的宽度处理节点值再把下一层的左右孩子入队。103 题只不过在“处理节点值”这一步加了方向控制。我推荐的写法是维护一个boolean leftToRight或整数level % 2 0作为方向标记。每处理完一层标记取反。结合 Java 的LinkedList既可以当队列用也可以当双端队列用往头部插入用addFirst往尾部插入用addLast非常顺手。这里有一个很多教程没点透的细节必须先记录当前层的节点数量size queue.size()再开始内层循环。如果不记录内层循环一定把已经加入队列的下一层节点也当成当前层处理导致层级错乱。这个坑几乎所有初学者都会踩一次。2.3 空间复杂度的工程化分析为什么双端队列不浪费有人会问“既然每层节点值都已经放在结果集里了为什么还要用双端队列直接Collections.reverse不就完了”这个问题问得好。从纯算法角度前者并不省空间因为两种方式都额外存储了当前层的节点值。但从代码维护角度双端队列把“方向”语义集中在一个集合操作上读代码的人一眼就能看出“这层是反的”而不需要额外找 reverse 的位置。在实际工程里如果我们用 Java 的ArrayList收集每一层然后用Collections.reverse反转那在 ArrayList 内部会做一次元素交换虽然时间复杂度还是 O(n)但如果你在追求极致性能的底层系统里这种多余的交换是可以避免的。这也是大量题解选择双端队列的原因——不是炫技而是少做无用功。3. 实操过程与核心代码实现103 题完整手写记录3.1 从零写代码TreeNode 定义、队列初始化、边界用例开始之前先确认我们的基础结构。LeetCode 平台已经给出了二叉树节点定义public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }核心方法签名是public ListListInteger zigzagLevelOrder(TreeNode root)写代码前我最喜欢先在草稿纸上列边界用例root null直接返回空列表不需要单独判空分支以外的处理。只有根节点返回[[root.val]]方向左→右。满二叉树三层以上第二层从右往左第三层从左往右。只有左孩子的“斜树”每一层只有一个节点方向标记无实际影响但不能报错。这些用例能在你写完代码后立刻进入自查状态比直接提交省时间。3.2 完整代码与逐行拆解双端队列方案的 Java 实现下面是我比较喜欢的实现已经多次在 LeetCode 上提交通过跑满 100% 左右的时间class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode 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); } } result.add(level); leftToRight !leftToRight; } return result; } }逐行拆一下queue.offer(root)把根节点放进队列while (!queue.isEmpty())控制层序遍历队列清空意味着所有节点处理完毕。进入内层循环前size queue.size()固定当前层节点数循环里poll()弹出队首节点然后根据方向标记决定addLast还是addFirst。这里的关键是把子节点加入队列的操作发生在poll()之后并且方向标记不会影响子节点的入队顺序——它们始终从左到右入队只是当前层的输出顺序被反转。最后leftToRight !leftToRight翻转方向。3.3 不用双端队列的备选方案列表反转写法及对比如果你对双端队列不感冒也可以写更朴素的版本用普通QueueTreeNode收集节点每层收集到一个ListInteger如果当前是偶数层且不为第一层就把这个列表反转class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); int levelIndex 0; while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } if (levelIndex % 2 1) { Collections.reverse(level); } result.add(level); levelIndex; } return result; } }这个版本的好处是思路直白不依赖读者对双端队列的熟悉程度坏处是每层反转多一次 O(n) 操作。如果在面试中写这个版本最好主动向面试官提一句“这里我每层反转一次额外 O(n) 时间但总复杂度仍是 O(n) 量级只是多一倍常数”一般也能过关。3.4 复杂度分析时间、空间与 LeetCode 判定结果时间复杂度每个节点恰好入队一次、出队一次节点值为 val 的操作也是常数时间所以总时间复杂度 O(n)这里 n 是二叉树节点总数。双端队列的addFirst和addLast都是 O(1)所以没有额外摊还成本。空间复杂度队列中最多同时存在一层节点满二叉树最大层的节点数量约等于 n/2所以空间复杂度 O(n)。输出用的二维列表也占 O(n) 空间这是题目要求返回的数据结构不算额外空间。在 LeetCode 上提交时双端队列版本在 Java 提交记录里通常能稳定在 1ms 左右内存 40MB 上下在 103 题里算是非常健康的成绩。如果你用列表反转版本时间会在 2ms 左右差距并不大所以我自己刷题时更看重代码可读性而不是为了快 1ms 牺牲语义清晰度。4. 反转链表 II 实操详解从 dummy 节点到头插法4.1 反转链表 II 的边界陷阱第 m 个节点可能是头节点现在切换到真正意义上的“反转链表 II ”LeetCode 92。题目会给你一个单链表的头节点 head以及两个整数 m 和 n要求反转从位置 m 到位置 n 的链表节点m、n 从 1 开始计数。比如1 - 2 - 3 - 4 - 5m2n4结果是1 - 4 - 3 - 2 - 5。这道题最大的坑是如果 m1你要反转的区间从链表的头节点开始。此时“区间前驱”不存在如果代码里贸然访问pre.next必然导致空指针。解决办法是经典的 dummy 技巧new 一个虚拟头节点让它指向 head然后从 dummy 开始走 m-1 步找到真正的“前驱节点”。这样即使 m1前驱也是 dummy不用单独写 if 分支。这个技巧我愿称之为“局部整形手术里的保底切口”几乎所有局部链表操作的题目都可以先加 dummy 再动手。4.2 迭代解法三指针头插法的完整推导先介绍我推荐的迭代法——头插法。它的核心思想是在反转区间内每次把“当前节点”从原位置摘下来插入到区间前驱的后面。整个过程只需要一个指向“前驱”的指针以及两个游标指针。假设链表为1 - 2 - 3 - 4 - 5m2n4加dummy令dummy.next headpre dummy。让pre前进 m-1 步即 m2 时前进 1 步pre指向节点 1。此时start pre.next节点 2then start.next节点 3。执行反转循环 n-m 次。循环体只有三行start.next then.next、then.next pre.next、pre.next then。这个循环做完节点 3 被插到 pre 后面链表变成1 - 3 - 2 - 4 - 5。继续循环then更新为原来的then.next节点 4再执行三行链表变成1 - 4 - 3 - 2 - 5。返回dummy.next。写成代码class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 0; i m - 1; i) { pre pre.next; } ListNode start pre.next; ListNode then start.next; for (int i 0; i n - m; i) { start.next then.next; then.next pre.next; pre.next then; then start.next; } return dummy.next; } }这三行指针操作是经典中的经典但也是最容易写晕的地方。我建议拿纸笔画一下“摘节点、接前驱、补 next”这三步不要背代码。只要画一次你就会发现整个过程就是把then节点强行拉到pre后面同时保证start永远指向区间内的第一个节点。4.3 递归解法从反转前 N 个节点到反转区间除了迭代头插法递归解法也是个不错的选择虽然代码看起来更抽象。思路是先定义一个辅助函数reverseN(ListNode head, int n)用来反转链表的前 n 个节点然后递归找到第 m 个节点把它当作reverseN的新链表头反转前 (n-m1) 个节点最后把第 m-1 个节点的 next 指回新的头。reverseN的递归实现需要保存一个“后继节点”因为反转前 n 个节点后原来的第 n1 个节点要作为新的链表尾部接上。代码class Solution { ListNode successor null; public ListNode reverseBetween(ListNode head, int m, int n) { if (m 1) { return reverseN(head, n); } head.next reverseBetween(head.next, m - 1, n - 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; } }递归版本在 LeetCode 上同样能过但它的难点在于reverseBetween(head.next, m-1, n-1)的边界参数变化。如果 m2、n4递归到下一层时变成 m1、n3正好就是“反转前 3 个节点”语义是完整的。这个版本写起来很优雅但在面试高压环境下容易卡壳。我的建议是取舍时间紧张优先写迭代头插如果面试官追问“能不能用递归”再切换到这个方案。4.4 两种方案的复杂度对比与选型建议时间上迭代和递归都是 O(n)只需要遍历一遍或两遍链表。空间上迭代是 O(1)递归最坏情况下 O(n) 递归栈空间如果区间接近链表头且 n 很大递归深度最大为 n。工程上链表长度不确定递归栈有溢出风险所以如果代码要用在生产环境我更推荐迭代。但如果你的目标是应对面试两者都应该能默写。面试官问链表反转系列问题时经常从 206 问到 92 再问到 25K 个一组翻转。206 是基础92 是边界控制25 是综合应用。你如果能用迭代把 92 讲得清楚说明指针操作已经过关再顺手用递归补充一个思路说明你理解了链表的天然递归结构面试官对你的数据结构功底会高看一眼。5. 常见问题与排查技巧实录5.1 103 题高频报错与调试清单我在给网友做 code review 时发现 103 题最常见的报错有以下四个第一个是空指针异常没有先判root null直接queue.offer(root)在空树上直接 NPE。解决方案是在方法开头加一行。第二个是层级错乱内层循环里没有用size固定当前层数导致一层处理完后下一层节点也被塞进了同一个 level 列表。排查方法是在while循环开头打印queue.size()你会惊讶地发现它一直在变大。第三个是方向标记反了有人从第二层开始用addFirst结果第一层也反了。因为题目要求根节点这一层从左到右也就是第 0 层不反转。方向标记初始值应该为true代表左到右每层结束后!leftToRight。第四个是返回值类型写错LeetCode 要求ListListInteger有人手滑写成ListArrayListInteger编译器直接报错。这个不涉及算法但很常见写代码前看清泛型。5.2 92 题高频报错与排查思路92 题我见过最多的错误是把反转区间的循环次数写错。for (int i 0; i n - m; i)是标准写法但很多人会按“反转 n-m1 个节点”去写导致多循环一次链表结构被打乱。我建议在草稿纸上用一个 5 节点链表m2n4手动模拟循环次数。反转 2 到 4 一共涉及 3 个节点但循环只需要执行 2 次因为第一个节点已经在初始时被固定为start了只有then需要被反复“摘除并插入”。第二个容易掉的坑是没有返回值。方法签名要求返回ListNode但有人直接在原地操作head最后返回head。这在 m1 时不成立所以一定要用dummy.next作为返回值。第三个坑是忘记处理start.next then.next的顺序。如果先改动then.next pre.next再改start.next会丢失then原来的后继链表直接断成两截。我更喜欢用“先摘后接、先断后连”的口诀来记先让start跳过then再让then指向pre的下一个最后让pre指向then。这三步顺序不能乱。5.3 避坑经验从“能过”到“写得让人放心”很多人刷题只追求提交通过但真正面试时面试官更在乎你的代码是否“让同事放心”。我自己的标准有三个第一边界条件在最前面处理。root null、head null、m n这类情况应该在函数开头直接写掉而不是散落在代码中间。第二变量名有业务语义。不要用p、q、r这种单字母用pre、start、then、leftToRight会让读代码的人瞬间明白你的思路。第三复杂指针操作旁边写注释。尤其是 92 题的三行指针操作如果不注释三天后你自己都看不懂。注释可以写“将 then 节点摘出并插入到 pre 之后”也能在面试时引导面试官理解你的思路。5.4 血泪经验周赛中卡在 Bug 里的真实复盘我有一段时间沉迷 LeetCode 周赛结果在周赛 430 里遇到一道类似层序遍历的变体题就是因为在addFirst和addLast的选择上写反了方向白掉了 20 分钟调试。复盘下来问题出在我没有把“层号从 0 开始”和“方向标记”这两件事在草稿纸上画清楚。后来我养成一个习惯每道涉及奇偶层、交替方向的题都在代码前画一个 3 层的示意图标注每一层的方向。这个习惯帮我避免了很多无意义的 debug。特别是 103 这种“看着简单、做起来容易错”的题画图比背书靠谱得多。另一个习惯是写完后先跑自己的边界用例再提交。LeetCode 的测试用例虽然全但有些隐含的边界比如只有一个节点的树被测试覆盖到不代表你能一次写对。6. 面试延伸与题单串联从 103 到一整个算法模块6.1 二叉树的层序变体题单102、103、107、199如果你刷透了 103其实相当于打通了一个“二叉树层序家族”102 题普通层序遍历从左到右最基础的 BFS 模板。103 题锯齿形层序遍历在 102 基础上加方向标记。107 题自底向上的层序遍历 II只需要在 102 的结果集上做一次Collections.reverse(result)。199 题二叉树的右视图本质上只需要每层最后一个节点。这四题可以放在一天内刷完因为它们共用同一套 BFS 模板只是对每层结果的加工方式不同。面试时如果被问到“你会层序遍历吗”你可以在三分钟内把四个变体全部讲完面试官会觉得你不只是背题而是真正理解了模型的泛化能力。6.2 链表反转系列206、92、25、24 的递进关系链表反转家族同样有清晰的难度阶梯206 题反转整个链表迭代三指针或递归都行是“开胃菜”。92 题反转区间也就是本文讲的这道关键在 dummy 和区间定位。24 题两两交换链表中的节点可以看作是 m、n 交替的固定区间反转。25 题K 个一组翻转链表是终极版需要分组定位、递归或迭代处理每一组。我的刷题建议是先 206再 92再 24最后 25。每一步都在上一步的代码上做增量修改而不是每道题都从零开始。6.3 二分与层序的暗线073 爱吃香蕉的狒狒带来的启发热词里的“073 爱吃香蕉的狒狒”是 LeetCode 875 题的昵称考察二分查找。表面上看跟二叉树、链表没关系但它和 103 一样都有一个“看似需要模拟、实际可以结构化拆解”的共性。爱吃香蕉的狒狒要求你在 H 小时内吃掉 N 堆香蕉每堆里有若干根香蕉求最小速度 K。暴力模拟就是从 1 开始试速度一直到能吃完二分做法是直接对 K 的可行性做“判断”把时间复杂度从 O(maxPile * N) 降到 O(N * log maxPile)。这个思路跟 103 有什么关系103 的层序遍历本质上也是“用队列按结构扫描而不是递归地枚举路径”。当你刷多了就会发现很多中等题考察的不是某个高深算法而是你有没有用对遍历模板和边界控制。这也是我为什么建议大家在刷题时做“模块化总结”而不是按题号记忆。7. 个人经验与后续扩展建议最后聊点实在的。我在实际使用中发现103 和 92 这两道题隔三差五就会出现在不同公司的笔试里而且经常被改造成“业务化”的包装比如 103 变成“二叉树之字形打印报表”92 变成“链表区间重组”。换了个壳内核完全没变。所以我把这两道题的模板打印出来贴在工位上每次换工作刷题前先在白板上默写一遍再开始刷别的题。另外还有一个建议刷题不要贪多尤其是中等题一道题用不同解法各写一遍比如 92 题先写迭代再写递归103 题先写双端队列版本再写列表反转版本。这个过程能帮你把“背代码”升级成“理解数据结构的行为”。等哪一天你能不看参考代码在纸上画图推导出“start.next then.next”这三行你才算真正通关。如果你正准备面试可以把这篇文章里的 5.3 节和 5.4 节当成自查清单先确认能写出边界处理再确认能说清复杂度最后确认能答出“为什么用双端队列 / 为什么用 dummy 节点”。这三关过了即使面试官临时变形你也有底气接招。3800 多字的篇幅听起来很长但每一段几乎都对应一个真实的踩坑现场把这些消化透比刷十道重复题更值。