1. 这道拆分题到底在考什么题目解读与难点定位1.1 最常见的题目表述与隐藏考点单链表拆分是我在带A同学刷题时反复被问到的一类题目。题目通常这样描述给定一个单链表和一个值 x要求把链表中所有小于 x 的节点排在所有大于等于 x 的节点之前同时保持原来的相对顺序。这道题看起来人畜无害很多初学者第一反应是“这不就是遍历一遍把节点分到两个队列里吗”但真动手写代码时问题就来了头节点会变怎么办链表是单向前进怎么回头断开之后怎么接回去写出来的程序要么在某个边界用例上报错要么逻辑跑不通要么空间复杂度超标。实际上这道题考察的核心不是“会不会比较大小”而是三个层面的能力对链表指针结构的理解、对节点断开与重接的掌控、对边界条件空链表、单节点、全部小于、全部大于等于的防御性思考。它是一道典型到不能再典型的链表操作题也是后续解决链表分区、链表排序、链表重排等问题的底层功底。1.2 “保持相对顺序”才是真正的题眼刷过链表题的人应该知道链表题往往不只有一种解法但不同解法之间的差距往往体现在“稳定性”上。题目要求保持原有相对顺序意思就是原来在前面的节点拆分后仍然在前面原来在后面的节点拆分后仍然在后面。举个例子链表是 3 - 1 - 4 - 2x 是 3。小于3的节点有 1 和 2它们在原链表里的顺序是 1 在前、2 在后所以拆分结果是 1 - 2 - 3 - 4。如果结果是 2 - 1 - 3 - 4虽然值的大小关系没毛病但仍然算错因为相对顺序被破坏了。这个要求很关键它直接否定了某些看起来很聪明的做法。比如有些人把节点值存到数组里排序后再重建链表——这样虽然最终大小关系正确但相对顺序很容易错而且空间复杂度从 O(1) 变成了 O(n)实际上是把链表题做成了数组题失去了练习意义。正确思路应该是只调整指针的指向不改变节点在内存中的相对位置通过“拆——分——接”三步完成。1.3 为什么链表题看着简单写起来总翻车我在实际辅导中观察到一个非常普遍的现象学习者拿到链表题习惯性地用数组思维去思考。数组操作靠下标链表操作靠指针数组删除中间元素需要搬移数据链表删除中间元素只需要改一个指针。思维模型不同写出来的代码就很容易“想当然”。单链表还有一个反直觉的特点它是一个单向结构每个节点只知道下一个节点在哪不知道上一个节点在哪。这意味着一旦你把当前节点的 next 指针改了你就永远失去了访问它原先后继节点的入口除非你提前保存。很多人在遍历拆分时遍历指针被自己改乱了最后链表断成好几截输出结果只有第一个节点其他节点全部“丢失”。所以做这道题之前我建议你先建立两个习惯第一凡是修改 next 指针之前必须先把后继节点存到一个临时变量或另一个指针里第二凡是头节点可能变化的链表操作优先引入“虚拟头节点”dummy node避免为头节点的特殊情况写一堆 if-else。2. 原地拆分的核心原理虚拟头节点与指针切断2.1 为什么“不新建节点”是硬约束不少版本的题目明确要求只能改变节点的 next 指针不能新建额外节点。即使题目没写我也建议你坚持这个约束这才是这道题真正的训练价值。新建节点意味着什么意味着你每把一个节点归入某一侧就要 new 一个新节点并把值拷贝进去。这样做有两宗罪一是空间复杂度变成 O(n)失去了链表操作最重要的“原地修改”优势二是破坏了节点的身份链表题很多时候考验的正是“如何把现有节点重新组织成一棵新结构”而不是“拷贝值造一份新链表”。真正合格的拆分应该把原链表节点当作“积木”通过修改它们的 next 指针把它们重新拼成两条新的链。整个过程不申请任何额外节点空间复杂度 O(1)只借助几个指针变量移动。2.2 虚拟头节点解决头节点的“漂移”问题拆分链表时我们要把节点分别接到两条链上。比如小于 x 的节点接一条链大于等于 x 的节点接一条链。问题来了刚开始这两条链都是空的第一个满足条件的节点来的时候我们应该让它成为链的头节点。但当前节点是动态变化的你不知道第一个满足条件的节点什么时候会出现于是就需要专门判断“当前链是不是空的”来决定是否更新头节点。这种判断不复杂但写起来啰嗦而且很容易漏。更优雅的方案是为两条新链各设置一个虚拟头节点。虚拟头节点不存放实际数据只是一个占位符它的 next 才指向真实链表的第一个节点。有了虚拟头节点所有节点包括第一个的接入方式就完全统一了每次只需要让当前链的尾指针指向新来的节点然后更新尾指针。等遍历结束后返回虚拟头节点的 next就是拆分后的真实头节点。这是链表题里最常用的技巧之一我建议你把它当成条件反射。2.3 指针移动的条件和顺序陷阱拆分过程中两个尾指针比如 small_tail 和 large_tail分别记录两条链的最后一个节点。遍历指针 cur 负责扫描原链表。每一次循环要做三件事保存 cur 的下一个节点记为 nxt根据条件把 cur 接到 small_tail 或 large_tail 后面并移动对应尾指针把 cur 移动到 nxt继续下一轮。这里最容易踩的坑是第 2 步和第 3 步的顺序。你必须在把 cur 接入新链之后立刻更新对应的尾指针同时不能丢 nxt。如果你先移动 cur再考虑接入那 cur 已经指向下一个节点了当前节点就再也找不到了。另一个坑是接入时没有让 cur.next 先置空导致新链的尾部悄悄连着尚未处理的节点最后出现环或重复输出。我用一句话总结这种操作的节奏先保存后继再接当前最后前进。这句话听着简单但真正写代码时你能不能坚持住决定了这道题你能不能一次写对。3. 一套能跑的代码Python实现与逐行解释3.1 节点结构定义链表题在绝大多数语言里都需要先定义节点。Python 里最简洁的写法是class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这里的 next 默认为 None意味着一个节点创建出来时默认就是链表的末尾。很多初学者不习惯这个写法总觉得要显式传一个 None。其实默认为 None 反而更安全因为你 new 一个节点后如果忘记设置 next它也不会指向无效地址。3.2 完整拆分函数下面给出一份可以直接运行的拆分函数。假设函数名为partition_list它接收链表头节点head和划分值x返回拆分后的新头节点。def partition_list(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 # 1. 先保存后继 if cur.val x: small_tail.next cur # 2. 接入小值链 small_tail cur # 3. 更新尾指针 else: large_tail.next cur large_tail cur cur nxt # 4. 前进 # 切断大值链末尾可能残留的引用 large_tail.next None # 把两条链拼接起来 small_tail.next large_dummy.next return small_dummy.next这段代码只有十几行但里面的细节值得逐行琢磨。注意看nxt cur.next被放在最前面这是整个循环的安全保证。如果没有这一行当cur.next被覆盖后循环就没办法继续向后遍历了。large_tail.next None这一行很多人会漏写。原因是原链表最后一个节点不一定被分到大值链。比如链表中最后一个节点恰好小于 x那它会被接到小值链上而大值链的尾节点还保留着指向原链表后续节点的引用可能造成环。所以无论最后大值链有没有节点都建议显式切断。3.3 核心步骤分析循环不变式为了确保代码逻辑正确我们可以采用算法分析里常用的“循环不变式”来验证。这个循环维持的不变量是每次循环开始时cur 指向原链表中尚未处理的第一个节点small_dummy.next 指向的小值链已经包含所有已处理且小于 x 的节点且保持原有相对顺序large_dummy.next 指向的大值链已经包含所有已处理且大于等于 x 的节点且保持原有相对顺序。只要这个不变量在循环体结束之后依然成立整个算法就是正确的。循环结束时 cur 为 None说明所有节点都处理完毕两链各就各位。最后把两条链拼接返回小值链头任务完成。这种证明方式虽然不需要写进代码里但我建议你在学习时养成这个习惯。链表操作的代码往往很短短到“看起来对了”但短代码恰恰最容易隐藏边界问题。用不变量去检验每一行修改是否破坏了链条结构比反复调试更快。4. 测试与调试怎么确认拆分结果是对的4.1 自己写驱动代码构造测试链表算法题写完之后不能只看代码就觉得自己会了。我见过太多人写完了不测试一提交就挂在某个边界用例上。链表题尤其需要手动构造测试数据因为链表输入不像数组那样方便你没办法直接用中括号写一个链表。构造链表的常用手法是反向拼接从尾节点开始逐一向前创建节点。比如要构造链表 1 - 4 - 3 - 2 - 5可以这样写def build_list(values): dummy ListNode(0) tail dummy for v in values: tail.next ListNode(v) tail tail.next return dummy.next head build_list([1, 4, 3, 2, 5])这种写法和上一节拆分代码的尾插法如出一辙。你会发现链表题的很多技巧是互通的尾插、虚拟头、尾指针几乎无处不在。多练几道题之后这些模式会自动在你脑中建立索引。4.2 打印结果的辅助函数设计测试链表结果不能直接 print(head)因为打印对象内存地址对排查没有帮助。你需要一个专门的打印函数def print_list(head): vals [] while head: vals.append(str(head.val)) head head.next print( - .join(vals))这个函数遍历链表把节点值收集到列表里再用箭头连接打印。输出的可读性很重要1 - 4 - 3 - 2 - 5比print(head)输出的__main__.ListNode object at 0x...直观一万倍。调试链表题本质上是可视化问题。你看不到节点之间的链接关系就只能靠打印来“还原”结构。打印辅助函数虽然简单但在你排查复杂链表题时它的价值不亚于 IDE 里的断点。4.3 手动模拟一遍两个关键指针的变化写完测试代码后建议挑一条有代表性的测试链手动过一遍循环验证每个指针的状态变化。我们以链表1 - 4 - 3 - 2 - 5x3 为例做一次纸面推演初始状态small_dummy、large_dummy 都是独立的虚拟头节点small_tail、large_tail 分别指向它们cur 指向节点 1。第一步cur 是 11 3接入小值链。small_tail.next 指向 1small_tail 变为节点 1cur 移动到 4。第二步cur 是 44 3接入大值链。large_tail.next 指向 4large_tail 变为节点 4cur 移动到 3。第三步cur 是 33 3接入大值链。large_tail 变为节点 3cur 移动到 2。第四步cur 是 22 3接入小值链。small_tail 变为节点 2cur 移动到 5。第五步cur 是 55 3接入大值链。large_tail 变为节点 5cur 变为 None循环结束。最后切断 large_tail.next原本它指向 None切断与否看不出来但逻辑上要执行再把 small_tail.next 指向 large_dummy.next也就是节点 4。最终小值链是 1 - 2大值链是 4 - 3 - 5拼接结果是 1 - 2 - 4 - 3 - 5。注意这里 3 出现在 4 之后看起来“不排序”但结果完全正确因为题目不要求整体排序只要求小于 x 的在前。这个推演过程不需要电脑拿纸笔就能做。我强烈建议每一位初学者每做一道链表题都至少手动推演一遍。这个习惯能极大减少“凭感觉写代码”带来的隐性错误。5. 边界情况逐个击破空链表、单节点、全同侧与重复值5.1 空链表与单节点空链表是最容易处理的边界情况但也是最容易在写代码时漏掉的。如果 head 本身就是 None那么循环体直接不执行最后 small_tail.next large_dummy.next此时 large_dummy.next 是 None返回的也是 None。这个行为恰好是正确行为空链表拆分后还是空链表。但如果你没有用虚拟头节点而是试图判空后再处理你可能会多写很多防御代码。用好虚拟头节点后空链表自动被覆盖。单节点链表比如只有一个节点 5x3。此时 5 3所以它会被接到大值链上。small_tail.next 被设置为 large_dummy.next节点 5最终返回的链表就是 5。看起来拆分没有发生但这正是正确结果因为没有节点小于 x所以小值链为空全部节点留在大值链中。5.2 所有节点都小于 x / 所有节点都大于等于 x当所有节点都小于 x 时整个遍历过程中 large_tail 始终指向 large_dummy它的 next 始终为 None。循环结束后large_tail.next None 这行仍然执行认真想想会发现这行代码在这个情况下其实是多余的——large_dummy.next 本来就是 None。但多写一行无害而且能覆盖其他异常情况所以我选择保留。当所有节点都大于等于 x 时情况反过来small_tail 始终指向 small_dummysmall_tail.next 最终被设置为 large_dummy.next也就是大值链的头节点。返回的结果就是整条原链表。这也完全正确。这一类“极端值分布”用例我建议你在测试时至少跑一遍。它们往往能暴露你对特殊情况处理的不够谨慎而且只需要改动构造链表的数据即可成本非常低。5.3 重复值节点和逆序输入重复值节点的情况比如链表2 - 2 - 2x2。因为条件判断是cur.val x所以三个节点全都走大值链最终返回的原链表。注意这个行为依赖判断条件的设计。如果你写成cur.val x那小于等于的节点会进小值链结果完全不同。题目里通常写的是“小于 x 的在前大于等于 x 的在后”所以使用判断才是符合要求的。逆序输入比如5 - 4 - 3 - 2 - 1x3。手动过一遍你会发现小值链最终是 2 - 1大值链最终是 5 - 4 - 3。相对顺序 2 在 1 前面、5 在 4 前面、4 在 3 前面全都保留下来了。这就是“稳定拆分”的含义。如果你把判断条件写反了比如当成逆序输入会直接暴露问题大值链变成了 5 - 4小值链变成 3 - 2 - 1结果反而是一个降序排列。这个现象很有迷惑性因为不少人在随机测试时可能“恰好”觉得它挺合理。所以测试用例一定要覆盖升序、降序、全相同、随机混合四类少一类都可能留下隐患。6. 从这道题延伸出去的变体奇偶拆分、多段拆分与排序辅助6.1 按节点位置奇偶拆分链表拆分的核心思路完全可以迁移到其他条件上最常见的一个变体是“按位置奇偶拆分”。题目要求把所有奇数位置的节点放在前面偶数位置的节点放在后面奇偶内部保持原有相对顺序。实现思路几乎一模一样只是判断条件从“值小于 x”变成“当前节点在原链表中的位置是奇数还是偶数”。你可以在循环外部维护一个计数器index每处理一个节点加 1然后根据index % 2决定接到哪条链上。也可以用两个指针交替前进一个走一步、一个走两步但那个方法更复杂写起来也容易乱不如计数器直白。这道变体题的存在说明了一个更深层的道理拆分的核心不是比较大小而是“按某种规则把节点分流到不同链上”。只要掌握了虚拟头节点 尾指针 先存后继这三板斧换成任何规则都不怕。6.2 按自定义条件拆分并反转某一段有些题目会把拆分和反转结合。比如要求“把所有 val 在 [L, R] 区间内的节点拆出来并且按逆序放到链表尾部”。这种题乍一看复杂但你可以拆成两个子问题先按区间条件拆分出“区间内”和“区间外”两条链然后对区间内那条链做反转最后拼接。反转单链表本身也是一道经典题核心套路是用三个指针 pre、cur、nxt 逐步逆转。当你把拆分练熟后这种组合题对你来说就不再有“看不懂”的障碍剩下的只是把两个已知技能叠加使用。这也解释了为什么我在文章开头强调“单链表拆分是很多复杂链表题的地基”。地基打得牢组合题才能做得快。6.3 用拆分思想辅助链表排序再往上走拆分还是链表归并排序的前置操作。链表归并排序的基本流程是找中点把链表切成两半递归排序两半然后合并两个有序链表。这里的“找中点切两半”本质上就是一个按位置拆分的变体——只不过不是按奇偶拆而是按前半段和后半段拆。找中点的经典做法是快慢指针快指针每次走两步慢指针每次走一步快指针到达末尾时慢指针恰好在中点。找到中点后把中点前一个节点的 next 置为 None链表就像被剪刀剪断一样分成两半。这个过程和拆分中的“切断末尾引用”逻辑完全一致。当你学到这里再回头看单链表拆分例题就会发现它不再是一道孤立的题目而是一张算法知识网络中的关键节点。向前它连接基础遍历技巧向后它连接归并排序、链表重排、K 组翻转等一系列进阶操作。7. 我在反复刷这道题过程中积累的几点体会拆分链表这道题我在不同阶段反复写过好几遍每次都有新收获。第一遍写得磕磕绊绊各种断链第二遍开始习惯性地引入虚拟头节点第三遍已经能做到不看任何参考直接在白板上把代码写对。这个过程的转变核心不在于记住了代码而在于建立了一套稳定的链表操作“肌肉记忆”。我特别想强调一点很多人学习链表题时喜欢对着代码一行一行背诵。但我建议你反过来先理解两条链的“生长过程”再手推一轮指针变化最后再动手写。只有你在纸上成功模拟过一次代码才是你想出来的而不是背下来的。测试代码也是一个不可跳过的重要环节。我现在做链表题时几乎每次都会先在本地写一个小的测试脚本构造几组典型输入打印结果确认无误后再提交。看起来多花了几分钟实际上避免了反复试错浪费的时间属于典型的“磨刀不误砍柴工”。还有一个容易被忽略的小技巧如果你在写拆分代码时发现结果链表出现循环或重复别急着调逻辑先检查是不是没有切断大值链的尾指针。这个问题我见过不下十次几乎每个人都会踩一次。记住任何把多条链拼接起来的问题连接处都是高危区域必要时可以用纸笔把最终的 next 指向画出来。最后再分享一个扩展建议刷完这道题后试着不看任何参考把按奇偶位置拆分和按区间拆分这两个变体也实现一遍。如果这两道也能顺利写对说明你真的掌握了“链表分流”这一类问题而不是仅仅背下来了这一个解法。
