分割链表这道题对准备算法面试的人来说出镜率相当高。它是《程序员面试金典》里的原题编号 02.04同时在 LeetCode 上也有一个几乎一样的版本——86 号题「分隔链表」。题目本身很直白给定一个单链表和一个基准值 x把所有小于 x 的节点移动到大于等于 x 的节点之前。但就是这道看似简单的题我在模拟面试里见过不少人翻车有的是把问题想复杂了有的是指针处理出错直接死循环。我第一次做这道题的时候也走过弯路总想着把 x 单独拎出来放在链表中间折腾了半天代码写了一堆分支结果还是错的。后来才想明白这道题的重点根本不是「x 放哪」而是「怎么高效地把一条链表按条件拆成两段、再接回去」。这篇文章我会把题目语义、两种主流解法、复杂度分析、边界条件以及面试官最爱追问的几个点全部拆开讲一遍。无论你是刚开始刷题的新手还是准备冲刺大厂面试的进阶选手都能拿到可以直接照着用的东西。1. 题目拆解面试题 02.04 分割链表到底在考什么1.1 先看懂题目本身再动手原题描述非常短以 x 为基准分割链表使得所有小于 x 的节点排在大于等于 x 的节点之前。给出的示例是输入3 - 5 - 8 - 5 - 10 - 2 - 1x 5输出3 - 1 - 2 - 10 - 5 - 5 - 8我第一次看到这个输出是很困惑的。输入中小于 5 的节点依次是 3、2、1按照原始顺序排应该是 3 - 2 - 1怎么输出变成了 3 - 1 - 2原因在于这本书的原始版本只要求「小于 x 的节点全部在大于等于 x 的节点前面」并没有要求保持每个分区内部原来的相对顺序。所以 3 - 1 - 2 是合法的3 - 2 - 1 也合法只要左右分区对了就行。但这里有一个坑如果只按「不要求稳定性」的思路来写你写出的代码很可能过不了 LeetCode 86。LeetCode 86 的题目描述里明确加了一句「保留每个分区中节点的初始相对位置」。所以我的建议是从一开始就用稳定拆分的思路做题——也就是遍历时保持每条子链内部的原始相对顺序。这样写出来的解两个平台都能通过而且代码量并不会变多。这个选择我后面会反复强调因为它直接决定了你写出的代码是不是「通用解」。还要注意一点基准值 x 不需要出现在左右两部分的中间。示例里 x 5两个 5 都待在右边的分区里这是完全合法的。很多人会下意识地认为 5 必须单独作为一个分界点放在链表中间这个误解会让代码复杂度直接翻倍。记住一句话x 只是一个用来比较的阈值它不需要被移动到某个固定位置甚至可以不出现在链表里。1.2 为什么这道题在面试里出场率这么高分割链表不是一道难到让人挠头的题但它非常均衡地覆盖了链表操作的核心基本功。你仔细数一下就会发现遍历链表、虚拟头节点的使用、节点的摘除和拼接、尾指针的维护、边界条件处理——这些点在这道题里全部都要用到。面试官通过这一道题就能快速判断候选人是不是真的理解链表而不是只会背几个模板。更重要的是这道题非常适合延伸追问。你写完第一版面试官马上可以问最后为什么要把尾节点的 next 置空不用虚拟头节点怎么写能不能原地完成稳定解和不稳定解有什么区别空间复杂度是多少每一个追问都在考察你对指针关系的理解深度。所以下面我会按照「先讲最稳的解法再讲进阶解法最后把面试官可能问的点逐一点破」的顺序来组织内容你自己跟着过一遍基本就能应付这类链表重排题了。2. 最稳解法双虚拟头节点拆链法2.1 核心思路把一条链拆成两条再拼接拆链法的核心思路可以概括成一句话把原链表拆成两条子链一条装所有小于 x 的节点一条装所有大于等于 x 的节点遍历完之后再把两条子链首尾相接。我习惯用一个生活场景来类比。食堂打饭分两个队伍一边是素食窗口一边是荤菜窗口你只需要按标准把每个人分到两个队伍里最后让素食队伍末尾的人牵上荤菜队伍开头的人一条新的长队就排好了。链表的拆链法就是这个过程只不过分队的标准从「吃素还是吃荤」变成了「小于 x 还是大于等于 x」。实现上有两个关键点。第一必须使用虚拟头节点也就是 dummy node。为什么因为结果链表的头节点是不确定的。如果原链表的第一个节点小于 x那么小于链的第一个真实节点就是它如果原链表第一个节点大于等于 x那小于链的第一个真实节点可能是链表中间的某个节点甚至可能不存在。与其写一堆 if 来判断头节点不如直接用 dummy 占位最后统一返回 dummy.next。这个技巧在处理「头节点可能变化」的链表问题里几乎是万能钥匙。第二每条子链都要单独维护一个尾指针。因为我们是把原链表节点原地挂到两条子链上每个节点只有一个 next 指针你必须时刻知道每条子链当前接到哪里。尾指针指向当前子链的最后一个节点新节点来了就接在它后面然后更新尾指针。这个「虚拟头 尾指针」的组合模式在后面很多链表拆分题里都会反复出现。2.2 Java 与 Python 代码实现先看 Java 版本我尽量写最干净、最容易解释的版本public ListNode partition(ListNode head, int x) { ListNode smallDummy new ListNode(0); ListNode largeDummy new ListNode(0); ListNode smallTail smallDummy; ListNode largeTail largeDummy; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 关键先保存下一个节点 if (cur.val x) { cur.next null; smallTail.next cur; smallTail smallTail.next; } else { cur.next null; largeTail.next cur; largeTail largeTail.next; } cur next; } smallTail.next largeDummy.next; return smallDummy.next; }Python 版本逻辑完全一样只是换了个语法外壳def partition(head: ListNode, x: int) - ListNode: small_dummy ListNode(0) large_dummy ListNode(0) small_tail small_dummy large_tail large_dummy cur head while cur: nxt cur.next if cur.val x: cur.next None small_tail.next cur small_tail small_tail.next else: cur.next None large_tail.next cur large_tail large_tail.next cur nxt small_tail.next large_dummy.next return small_dummy.next如果你动手跑一遍示例会得到 3 - 2 - 1 - 5 - 8 - 5 - 10。细心的人会发现这跟题目给出的输出 3 - 1 - 2 - 10 - 5 - 5 - 8 不一样但这完全合法因为题目只要求小于 5 的节点在大于等于 5 的节点前面。左边三个节点都小于 5、右边四个节点都大于等于 5分区就成立。而且3 - 2 - 1这个结果还额外满足了 LeetCode 86 的稳定性要求等于一份代码覆盖两个平台。两个代码版本里我都做了两件容易被忽略的事第一遍历时先用next变量保存cur的下一个节点第二把cur挂到子链上之前先把cur.next置空。第一件是必须的因为挂载操作会改写cur.next如果不提前保存循环就没法继续。第二件是一种「安全写法」它确保每个节点挂到子链上时是干净的不会残留指向原链表其他节点的引用从根源上杜绝了成环的可能。如果你不想在循环里做这一步至少也要在最后拼接之前加上largeTail.next null。2.3 复杂度分析与关键细节说明时间复杂度是 O(n)一次遍历就能把所有节点分配完毕n 是链表长度。空间复杂度是 O(1)两个 dummy 节点是固定开销不随输入规模增长。这里说的「额外空间」是指除了返回结果之外占用的临时空间dummy 节点属于常数级开销所以是 O(1)。关于稳定性这个解法是稳定的。因为我们是按原始顺序依次遍历每个节点被挂到子链的顺序就是它出现在原链表中的顺序所以两条子链内部的相对顺序保持不变。前面说过这一点很重要它让这个解法同时满足面试题 02.04 和 LeetCode 86 的要求。最后说一个拼接时的细节smallTail.next largeDummy.next。有同学会写成smallTail.next largeDummy这是错的因为 largeDummy 是一个值为 0 的额外节点不是真实节点把它接上去结果链表最后就多出一个 0。记住dummy 只是占位符永远只能通过 dummy.next 拿真实节点。我 review 过的代码里这个问题出现过不止一次值得单独拎出来提醒。3. 进阶解法原地插入调整法不使用新链表3.1 边界指针 原地摘插的思路第二种解法不把链表拆成两条而是在原链表上通过「摘除 插入」完成重排。它的核心是维护一个边界指针我叫它lastSmall它指向当前已经确定的「小于 x 区域」的最后一个节点。遍历过程中如果遇到一个小于 x 的节点而且它刚好在lastSmall后面说明它已经在正确区域直接把lastSmall后移就行。如果它不在正确区域就把它从当前位置摘下来插入到lastSmall的后面然后更新lastSmall。大于等于 x 的节点不用动直接跳过。这个解法的空间优势在于完全不需要额外维护两条子链只需要一个 dummy 和一个边界指针。但代价是代码的指针操作明显变复杂尤其是在「摘除」和「插入」两个动作同时发生时顺序稍微写错就会导致节点丢失或者成环。所以我的总体建议是如果你对链表的指针操作还不够熟练面试时优先考虑拆链法如果你已经很有把握那可以在拆链法之后再补充这个解法展示更深的掌控力。3.2 代码实现与逐段讲解public ListNode partition(ListNode head, int x) { ListNode dummy new ListNode(0); dummy.next head; ListNode lastSmall dummy; ListNode prev dummy; ListNode cur head; while (cur ! null) { if (cur.val x) { if (prev lastSmall) { lastSmall cur; prev cur; cur cur.next; } else { prev.next cur.next; // 1. 摘除 cur cur.next lastSmall.next; // 2. 插入到 lastSmall 后面 lastSmall.next cur; lastSmall cur; // 3. 更新边界 cur prev.next; // 4. 继续处理下一个节点 } } else { prev cur; cur cur.next; } } return dummy.next; }逐段解释一下。第一个分支里如果prev lastSmall说明当前节点 cur 是「小于 x 区域」的下一个节点它已经在正确位置上我们只需要把lastSmall和prev同时移动到 cur然后继续前进。第二个分支是核心cur 小于 x 但不在正确位置。先执行prev.next cur.next把 cur 从链表中摘出来再执行cur.next lastSmall.next、lastSmall.next cur把 cur 插到边界之后最后lastSmall cur更新边界。这里最容易搞错的点是最后的cur prev.next。因为 cur 已经被摘走prev.next 已经被更新成 cur 原来的下一个节点所以下一个待处理节点就是prev.next。如果这里写成cur cur.next那 cur.next 指向的是刚插入位置后面的节点也就是原来正确区域的第一个节点会导致已经处理过的节点被重复处理直接死循环。每次讲到这个解法我都会特意在黑板上标出这一步因为它真的是重灾区。我的经验是不要在面试现场一边紧张一边现场推导这个代码最好提前在纸上把 3 - 5 - 8 - 5 - 10 - 2 - 1 这个例子完整走一遍走通了再上考场。走一遍你就会发现这个解法虽然指针操作多但每一步都是确定的只要把「摘除、插入、更新边界、移动到下一个」这四件事的顺序记牢就不会出错。3.3 两种解法对比与选题建议用一张表把两种解法的差异整理清楚对比维度双虚拟头节点拆链法原地插入调整法代码可读性高思路直观中低指针操作较多出错概率低逻辑清晰高容易漏边界条件额外空间2 个 dummy 节点1 个 dummy 节点时间复杂度O(n)O(n)空间复杂度O(1)O(1)稳定性稳定稳定面试推荐度首选方案进阶展示方案我的建议很明确面试中默认写拆链法。它简单、可解释、不容易出 bug面试官也最容易听懂你的思路。如果面试官追问「能不能用更少的额外空间」你再把原地插入法拿出来讲并说明两者都能保持稳定性。这样可以展示你脑子里有多个方案、能够根据约束条件做取舍是明显的加分项。反过来如果你一上来就写原地插入法写对了倒还好一旦指针绕晕把简单题做崩损失就大了。4. 易错点与边界情况排查实录4.1 五个必测边界用例速查表链表题最怕的不是主流程而是边界情况。下面这五个用例是我每次带人准备面试时都会强调的清单你可以直接拿来当自查表用例输入期望输出说明空链表head null, x 5null直接返回不能空指针异常单节点且小于 xhead 1, x 51原样返回全部小于 xhead 1 - 2 - 3, x 51 - 2 - 3大链为空全部大于等于 xhead 5 - 6 - 7, x 55 - 6 - 7小链为空x 不在链表中head 1 - 4 - 3 - 2, x 51 - 4 - 3 - 2基准值不需要存在第 5 种是很多人容易忽略的。x 只是一个阈值它完全可以不出现在链表里算法的比较逻辑不需要为 x 是否存在做任何特殊处理。这和数组版快排里的 partition 基准值不一样——数组版快排通常会把基准值交换到中间位置但链表版的这道题完全不需要你只需要拿每个节点的值和 x 比较该去哪边就去哪边。4.2 高频 bug 与排查方法我在实际写这道题和帮人 review 代码时遇到的典型 bug 基本可以归为三类这里按出现频率排序。第一类cycle detected。现象是提交后系统提示链表中存在环。原因几乎都是尾节点 next 没有置空。比如在拆链法中如果最后忘记给大链的尾节点 next 赋值 null而大链的最后一个节点在原链表里并不是最后一个它残留的 next 就可能指向某个已经被移到前面的节点形成环。排查方法很简单返回前遍历一次链表记录节点数如果超过原链表长度说明有环更直接的办法是采用我前面推荐的安全写法在挂载每个节点时就把它的 next 置空从根上杜绝问题。第二类结果链表少了节点。现象是输出链表的长度对不上。这种问题通常出在遍历指针的更新上。拆链法里如果你在挂载后用cur cur.next而不是用预先保存的next变量那么你拿到的 cur.next 已经被改成了当前子链的下一个节点于是原链表后面的节点就被跳过了。记住口诀先保存 next再操作 cur最后用保存的 next 前进。第三类dummy 节点泄漏进结果。如果你最后返回的是smallDummy而不是smallDummy.next结果链表的头会多出一个值为 0 的虚假节点。这个问题在本地测试时不容易被注意到但判题系统一定会判错。我见过好几个候选人 debug 了半天才发现是栽在这里。这三个 bug 我当年自己都踩过尤其是第一个当时调试了很久才明白是少了一句置空。所以我在正文里反复强调 next 的处理是真的有教训的不是空泛地讲理论。5. 面试加分项与题目延伸5.1 和 LeetCode 86 的关系面试题 02.04 和 LeetCode 86「分隔链表」本质上是同一道题。LeetCode 86 的题目描述是给你一个链表的头节点 head 和一个特定值 x对链表进行分隔使得所有小于 x 的节点都出现在大于或等于 x 的节点之前并且保留两个分区中每个节点的初始相对位置。注意最后这一句「保留初始相对位置」这就是 LeetCode 86 比面试题 02.04 多出来的明确要求。我在第 1 节讲过书的原版没有把稳定性写进题目描述但实际的主流题解和判题用例都默认采用稳定解法。所以结论很简单你按稳定拆链法写的解直接提交到 LeetCode 86 也一样能过。我的建议是两个题目都去提交一遍因为 LeetCode 的判题用例覆盖更全面能帮你把边界情况验证得更彻底。5.2 一类题多路链表拆分与相关变形搞懂了这道题你会发现一个很有意思的现象一批链表重排题的内核其实都是「按条件拆链再按规则拼接」。我把它们归为一类这里列几个典型代表LeetCode 328 奇偶链表把下标为偶数的节点放前面奇数下标的放后面。本质上就是按「下标奇偶」这个条件做双路拆分和分割链表唯一的区别是分区条件从「值的大小」变成了「下标的奇偶」。链表上的快速排序快排的 partition 步骤在单链表上实现时可以使用小值链、大值链配合当前 pivot 的拼接方式完成这几乎是分割链表加一层递归。三路拆分如果面试官接着问「把小于 -k、介于 -k 和 k 之间、大于 k 的节点分成三段」你只需要在拆链法的基础上多加一条子链、多维护一个尾指针逻辑完全不变。我带人准备面试时发现能写出分割链表的人很多但能把思路迁移到奇偶链表、三路拆分的人明显变少——而后者恰恰是面试官区分候选人的点。所以我的建议是做完这道题之后不要急着刷下一道花半小时把 LeetCode 328 做了再在纸上推一遍三路拆分的代码。这种「一题带一类」的刷题方式效率远高于盲目拼题量。最后再分享一个写链表题的小习惯。我每次写完链表操作代码都会在纸上画出操作前后的指针关系尤其是摘除和插入这两个动作。链表题绝大多数 bug 都出在指针更新顺序上——先改谁的 next、再改谁的 next顺序错了结果就全错了。以拆链法为例核心口诀是「先记住下一个再挂载当前最后移动尾指针」。这句话我在面试前会默念几遍面试时写这道题基本就不会翻车。 
长河君 · 2026/9/15 2:34:34 · 阅读 1.2k 分割链表算法解析：双虚拟头节点与原地插入法攻克面试题
分割链表这道题对准备算法面试的人来说出镜率相当高。它是《程序员面试金典》里的原题编号 02.04同时在 LeetCode 上也有一个几乎一样的版本——86 号题「分隔链表」。题目本身很直白给定一个单链表和一个基准值 x把所有小于 x 的节点移动到大于等于 x 的节点之前。但就是这道看似简单的题我在模拟面试里见过不少人翻车有的是把问题想复杂了有的是指针处理出错直接死循环。我第一次做这道题的时候也走过弯路总想着把 x 单独拎出来放在链表中间折腾了半天代码写了一堆分支结果还是错的。后来才想明白这道题的重点根本不是「x 放哪」而是「怎么高效地把一条链表按条件拆成两段、再接回去」。这篇文章我会把题目语义、两种主流解法、复杂度分析、边界条件以及面试官最爱追问的几个点全部拆开讲一遍。无论你是刚开始刷题的新手还是准备冲刺大厂面试的进阶选手都能拿到可以直接照着用的东西。1. 题目拆解面试题 02.04 分割链表到底在考什么1.1 先看懂题目本身再动手原题描述非常短以 x 为基准分割链表使得所有小于 x 的节点排在大于等于 x 的节点之前。给出的示例是输入3 - 5 - 8 - 5 - 10 - 2 - 1x 5输出3 - 1 - 2 - 10 - 5 - 5 - 8我第一次看到这个输出是很困惑的。输入中小于 5 的节点依次是 3、2、1按照原始顺序排应该是 3 - 2 - 1怎么输出变成了 3 - 1 - 2原因在于这本书的原始版本只要求「小于 x 的节点全部在大于等于 x 的节点前面」并没有要求保持每个分区内部原来的相对顺序。所以 3 - 1 - 2 是合法的3 - 2 - 1 也合法只要左右分区对了就行。但这里有一个坑如果只按「不要求稳定性」的思路来写你写出的代码很可能过不了 LeetCode 86。LeetCode 86 的题目描述里明确加了一句「保留每个分区中节点的初始相对位置」。所以我的建议是从一开始就用稳定拆分的思路做题——也就是遍历时保持每条子链内部的原始相对顺序。这样写出来的解两个平台都能通过而且代码量并不会变多。这个选择我后面会反复强调因为它直接决定了你写出的代码是不是「通用解」。还要注意一点基准值 x 不需要出现在左右两部分的中间。示例里 x 5两个 5 都待在右边的分区里这是完全合法的。很多人会下意识地认为 5 必须单独作为一个分界点放在链表中间这个误解会让代码复杂度直接翻倍。记住一句话x 只是一个用来比较的阈值它不需要被移动到某个固定位置甚至可以不出现在链表里。1.2 为什么这道题在面试里出场率这么高分割链表不是一道难到让人挠头的题但它非常均衡地覆盖了链表操作的核心基本功。你仔细数一下就会发现遍历链表、虚拟头节点的使用、节点的摘除和拼接、尾指针的维护、边界条件处理——这些点在这道题里全部都要用到。面试官通过这一道题就能快速判断候选人是不是真的理解链表而不是只会背几个模板。更重要的是这道题非常适合延伸追问。你写完第一版面试官马上可以问最后为什么要把尾节点的 next 置空不用虚拟头节点怎么写能不能原地完成稳定解和不稳定解有什么区别空间复杂度是多少每一个追问都在考察你对指针关系的理解深度。所以下面我会按照「先讲最稳的解法再讲进阶解法最后把面试官可能问的点逐一点破」的顺序来组织内容你自己跟着过一遍基本就能应付这类链表重排题了。2. 最稳解法双虚拟头节点拆链法2.1 核心思路把一条链拆成两条再拼接拆链法的核心思路可以概括成一句话把原链表拆成两条子链一条装所有小于 x 的节点一条装所有大于等于 x 的节点遍历完之后再把两条子链首尾相接。我习惯用一个生活场景来类比。食堂打饭分两个队伍一边是素食窗口一边是荤菜窗口你只需要按标准把每个人分到两个队伍里最后让素食队伍末尾的人牵上荤菜队伍开头的人一条新的长队就排好了。链表的拆链法就是这个过程只不过分队的标准从「吃素还是吃荤」变成了「小于 x 还是大于等于 x」。实现上有两个关键点。第一必须使用虚拟头节点也就是 dummy node。为什么因为结果链表的头节点是不确定的。如果原链表的第一个节点小于 x那么小于链的第一个真实节点就是它如果原链表第一个节点大于等于 x那小于链的第一个真实节点可能是链表中间的某个节点甚至可能不存在。与其写一堆 if 来判断头节点不如直接用 dummy 占位最后统一返回 dummy.next。这个技巧在处理「头节点可能变化」的链表问题里几乎是万能钥匙。第二每条子链都要单独维护一个尾指针。因为我们是把原链表节点原地挂到两条子链上每个节点只有一个 next 指针你必须时刻知道每条子链当前接到哪里。尾指针指向当前子链的最后一个节点新节点来了就接在它后面然后更新尾指针。这个「虚拟头 尾指针」的组合模式在后面很多链表拆分题里都会反复出现。2.2 Java 与 Python 代码实现先看 Java 版本我尽量写最干净、最容易解释的版本public ListNode partition(ListNode head, int x) { ListNode smallDummy new ListNode(0); ListNode largeDummy new ListNode(0); ListNode smallTail smallDummy; ListNode largeTail largeDummy; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 关键先保存下一个节点 if (cur.val x) { cur.next null; smallTail.next cur; smallTail smallTail.next; } else { cur.next null; largeTail.next cur; largeTail largeTail.next; } cur next; } smallTail.next largeDummy.next; return smallDummy.next; }Python 版本逻辑完全一样只是换了个语法外壳def partition(head: ListNode, x: int) - ListNode: small_dummy ListNode(0) large_dummy ListNode(0) small_tail small_dummy large_tail large_dummy cur head while cur: nxt cur.next if cur.val x: cur.next None small_tail.next cur small_tail small_tail.next else: cur.next None large_tail.next cur large_tail large_tail.next cur nxt small_tail.next large_dummy.next return small_dummy.next如果你动手跑一遍示例会得到 3 - 2 - 1 - 5 - 8 - 5 - 10。细心的人会发现这跟题目给出的输出 3 - 1 - 2 - 10 - 5 - 5 - 8 不一样但这完全合法因为题目只要求小于 5 的节点在大于等于 5 的节点前面。左边三个节点都小于 5、右边四个节点都大于等于 5分区就成立。而且3 - 2 - 1这个结果还额外满足了 LeetCode 86 的稳定性要求等于一份代码覆盖两个平台。两个代码版本里我都做了两件容易被忽略的事第一遍历时先用next变量保存cur的下一个节点第二把cur挂到子链上之前先把cur.next置空。第一件是必须的因为挂载操作会改写cur.next如果不提前保存循环就没法继续。第二件是一种「安全写法」它确保每个节点挂到子链上时是干净的不会残留指向原链表其他节点的引用从根源上杜绝了成环的可能。如果你不想在循环里做这一步至少也要在最后拼接之前加上largeTail.next null。2.3 复杂度分析与关键细节说明时间复杂度是 O(n)一次遍历就能把所有节点分配完毕n 是链表长度。空间复杂度是 O(1)两个 dummy 节点是固定开销不随输入规模增长。这里说的「额外空间」是指除了返回结果之外占用的临时空间dummy 节点属于常数级开销所以是 O(1)。关于稳定性这个解法是稳定的。因为我们是按原始顺序依次遍历每个节点被挂到子链的顺序就是它出现在原链表中的顺序所以两条子链内部的相对顺序保持不变。前面说过这一点很重要它让这个解法同时满足面试题 02.04 和 LeetCode 86 的要求。最后说一个拼接时的细节smallTail.next largeDummy.next。有同学会写成smallTail.next largeDummy这是错的因为 largeDummy 是一个值为 0 的额外节点不是真实节点把它接上去结果链表最后就多出一个 0。记住dummy 只是占位符永远只能通过 dummy.next 拿真实节点。我 review 过的代码里这个问题出现过不止一次值得单独拎出来提醒。3. 进阶解法原地插入调整法不使用新链表3.1 边界指针 原地摘插的思路第二种解法不把链表拆成两条而是在原链表上通过「摘除 插入」完成重排。它的核心是维护一个边界指针我叫它lastSmall它指向当前已经确定的「小于 x 区域」的最后一个节点。遍历过程中如果遇到一个小于 x 的节点而且它刚好在lastSmall后面说明它已经在正确区域直接把lastSmall后移就行。如果它不在正确区域就把它从当前位置摘下来插入到lastSmall的后面然后更新lastSmall。大于等于 x 的节点不用动直接跳过。这个解法的空间优势在于完全不需要额外维护两条子链只需要一个 dummy 和一个边界指针。但代价是代码的指针操作明显变复杂尤其是在「摘除」和「插入」两个动作同时发生时顺序稍微写错就会导致节点丢失或者成环。所以我的总体建议是如果你对链表的指针操作还不够熟练面试时优先考虑拆链法如果你已经很有把握那可以在拆链法之后再补充这个解法展示更深的掌控力。3.2 代码实现与逐段讲解public ListNode partition(ListNode head, int x) { ListNode dummy new ListNode(0); dummy.next head; ListNode lastSmall dummy; ListNode prev dummy; ListNode cur head; while (cur ! null) { if (cur.val x) { if (prev lastSmall) { lastSmall cur; prev cur; cur cur.next; } else { prev.next cur.next; // 1. 摘除 cur cur.next lastSmall.next; // 2. 插入到 lastSmall 后面 lastSmall.next cur; lastSmall cur; // 3. 更新边界 cur prev.next; // 4. 继续处理下一个节点 } } else { prev cur; cur cur.next; } } return dummy.next; }逐段解释一下。第一个分支里如果prev lastSmall说明当前节点 cur 是「小于 x 区域」的下一个节点它已经在正确位置上我们只需要把lastSmall和prev同时移动到 cur然后继续前进。第二个分支是核心cur 小于 x 但不在正确位置。先执行prev.next cur.next把 cur 从链表中摘出来再执行cur.next lastSmall.next、lastSmall.next cur把 cur 插到边界之后最后lastSmall cur更新边界。这里最容易搞错的点是最后的cur prev.next。因为 cur 已经被摘走prev.next 已经被更新成 cur 原来的下一个节点所以下一个待处理节点就是prev.next。如果这里写成cur cur.next那 cur.next 指向的是刚插入位置后面的节点也就是原来正确区域的第一个节点会导致已经处理过的节点被重复处理直接死循环。每次讲到这个解法我都会特意在黑板上标出这一步因为它真的是重灾区。我的经验是不要在面试现场一边紧张一边现场推导这个代码最好提前在纸上把 3 - 5 - 8 - 5 - 10 - 2 - 1 这个例子完整走一遍走通了再上考场。走一遍你就会发现这个解法虽然指针操作多但每一步都是确定的只要把「摘除、插入、更新边界、移动到下一个」这四件事的顺序记牢就不会出错。3.3 两种解法对比与选题建议用一张表把两种解法的差异整理清楚对比维度双虚拟头节点拆链法原地插入调整法代码可读性高思路直观中低指针操作较多出错概率低逻辑清晰高容易漏边界条件额外空间2 个 dummy 节点1 个 dummy 节点时间复杂度O(n)O(n)空间复杂度O(1)O(1)稳定性稳定稳定面试推荐度首选方案进阶展示方案我的建议很明确面试中默认写拆链法。它简单、可解释、不容易出 bug面试官也最容易听懂你的思路。如果面试官追问「能不能用更少的额外空间」你再把原地插入法拿出来讲并说明两者都能保持稳定性。这样可以展示你脑子里有多个方案、能够根据约束条件做取舍是明显的加分项。反过来如果你一上来就写原地插入法写对了倒还好一旦指针绕晕把简单题做崩损失就大了。4. 易错点与边界情况排查实录4.1 五个必测边界用例速查表链表题最怕的不是主流程而是边界情况。下面这五个用例是我每次带人准备面试时都会强调的清单你可以直接拿来当自查表用例输入期望输出说明空链表head null, x 5null直接返回不能空指针异常单节点且小于 xhead 1, x 51原样返回全部小于 xhead 1 - 2 - 3, x 51 - 2 - 3大链为空全部大于等于 xhead 5 - 6 - 7, x 55 - 6 - 7小链为空x 不在链表中head 1 - 4 - 3 - 2, x 51 - 4 - 3 - 2基准值不需要存在第 5 种是很多人容易忽略的。x 只是一个阈值它完全可以不出现在链表里算法的比较逻辑不需要为 x 是否存在做任何特殊处理。这和数组版快排里的 partition 基准值不一样——数组版快排通常会把基准值交换到中间位置但链表版的这道题完全不需要你只需要拿每个节点的值和 x 比较该去哪边就去哪边。4.2 高频 bug 与排查方法我在实际写这道题和帮人 review 代码时遇到的典型 bug 基本可以归为三类这里按出现频率排序。第一类cycle detected。现象是提交后系统提示链表中存在环。原因几乎都是尾节点 next 没有置空。比如在拆链法中如果最后忘记给大链的尾节点 next 赋值 null而大链的最后一个节点在原链表里并不是最后一个它残留的 next 就可能指向某个已经被移到前面的节点形成环。排查方法很简单返回前遍历一次链表记录节点数如果超过原链表长度说明有环更直接的办法是采用我前面推荐的安全写法在挂载每个节点时就把它的 next 置空从根上杜绝问题。第二类结果链表少了节点。现象是输出链表的长度对不上。这种问题通常出在遍历指针的更新上。拆链法里如果你在挂载后用cur cur.next而不是用预先保存的next变量那么你拿到的 cur.next 已经被改成了当前子链的下一个节点于是原链表后面的节点就被跳过了。记住口诀先保存 next再操作 cur最后用保存的 next 前进。第三类dummy 节点泄漏进结果。如果你最后返回的是smallDummy而不是smallDummy.next结果链表的头会多出一个值为 0 的虚假节点。这个问题在本地测试时不容易被注意到但判题系统一定会判错。我见过好几个候选人 debug 了半天才发现是栽在这里。这三个 bug 我当年自己都踩过尤其是第一个当时调试了很久才明白是少了一句置空。所以我在正文里反复强调 next 的处理是真的有教训的不是空泛地讲理论。5. 面试加分项与题目延伸5.1 和 LeetCode 86 的关系面试题 02.04 和 LeetCode 86「分隔链表」本质上是同一道题。LeetCode 86 的题目描述是给你一个链表的头节点 head 和一个特定值 x对链表进行分隔使得所有小于 x 的节点都出现在大于或等于 x 的节点之前并且保留两个分区中每个节点的初始相对位置。注意最后这一句「保留初始相对位置」这就是 LeetCode 86 比面试题 02.04 多出来的明确要求。我在第 1 节讲过书的原版没有把稳定性写进题目描述但实际的主流题解和判题用例都默认采用稳定解法。所以结论很简单你按稳定拆链法写的解直接提交到 LeetCode 86 也一样能过。我的建议是两个题目都去提交一遍因为 LeetCode 的判题用例覆盖更全面能帮你把边界情况验证得更彻底。5.2 一类题多路链表拆分与相关变形搞懂了这道题你会发现一个很有意思的现象一批链表重排题的内核其实都是「按条件拆链再按规则拼接」。我把它们归为一类这里列几个典型代表LeetCode 328 奇偶链表把下标为偶数的节点放前面奇数下标的放后面。本质上就是按「下标奇偶」这个条件做双路拆分和分割链表唯一的区别是分区条件从「值的大小」变成了「下标的奇偶」。链表上的快速排序快排的 partition 步骤在单链表上实现时可以使用小值链、大值链配合当前 pivot 的拼接方式完成这几乎是分割链表加一层递归。三路拆分如果面试官接着问「把小于 -k、介于 -k 和 k 之间、大于 k 的节点分成三段」你只需要在拆链法的基础上多加一条子链、多维护一个尾指针逻辑完全不变。我带人准备面试时发现能写出分割链表的人很多但能把思路迁移到奇偶链表、三路拆分的人明显变少——而后者恰恰是面试官区分候选人的点。所以我的建议是做完这道题之后不要急着刷下一道花半小时把 LeetCode 328 做了再在纸上推一遍三路拆分的代码。这种「一题带一类」的刷题方式效率远高于盲目拼题量。最后再分享一个写链表题的小习惯。我每次写完链表操作代码都会在纸上画出操作前后的指针关系尤其是摘除和插入这两个动作。链表题绝大多数 bug 都出在指针更新顺序上——先改谁的 next、再改谁的 next顺序错了结果就全错了。以拆链法为例核心口诀是「先记住下一个再挂载当前最后移动尾指针」。这句话我在面试前会默念几遍面试时写这道题基本就不会翻车。