企业官网建设流程全解析

1. 这道拆分题到底在考什么：题目解读与难点定位

1.1 最常见的题目表述与隐藏考点

单链表拆分，是我在带A同学刷题时反复被问到的一类题目。题目通常这样描述：给定一个单链表和一个值 x，要求把链表中所有小于 x 的节点排在所有大于等于 x 的节点之前，同时保持原来的相对顺序。

这道题看起来人畜无害，很多初学者第一反应是“这不就是遍历一遍，把节点分到两个队列里吗？”但真动手写代码时，问题就来了：头节点会变怎么办？链表是单向前进怎么回头？断开之后怎么接回去？写出来的程序要么在某个边界用例上报错，要么逻辑跑不通，要么空间复杂度超标。

实际上，这道题考察的核心不是“会不会比较大小”，而是三个层面的能力：对链表指针结构的理解、对节点断开与重接的掌控、对边界条件（空链表、单节点、全部小于、全部大于等于）的防御性思考。它是一道典型到不能再典型的链表操作题，也是后续解决链表分区、链表排序、链表重排等问题的底层功底。

1.2 “保持相对顺序”才是真正的题眼

刷过链表题的人应该知道，链表题往往不只有一种解法，但不同解法之间的差距，往往体现在“稳定性”上。题目要求保持原有相对顺序，意思就是：原来在前面的节点，拆分后仍然在前面；原来在后面的节点，拆分后仍然在后面。

举个例子，链表是 3 -> 1 -> 4 -> 2，x 是 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 负责扫描原链表。每一次循环要做三件事：

1. 保存 cur 的下一个节点，记为 nxt；
2. 根据条件把 cur 接到 small_tail 或 large_tail 后面，并移动对应尾指针；
3. 把 cur 移动到 nxt，继续下一轮。

这里最容易踩的坑是第 2 步和第 3 步的顺序。你必须在把 cur 接入新链之后，立刻更新对应的尾指针，同时不能丢 nxt。如果你先移动 cur，再考虑接入，那 cur 已经指向下一个节点了，当前节点就再也找不到了。另一个坑是，接入时没有让 cur.next 先置空，导致新链的尾部悄悄连着尚未处理的节点，最后出现环或重复输出。

我用一句话总结这种操作的节奏：先保存后继，再接当前，最后前进。这句话听着简单，但真正写代码时你能不能坚持住，决定了这道题你能不能一次写对。

3. 一套能跑的代码：Python实现与逐行解释

3.1 节点结构定义

链表题在绝大多数语言里都需要先定义节点。Python 里最简洁的写法是：

class ListNode: def __init__(self, val=0, next=None): 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 -> 5，x=3 为例做一次纸面推演：

初始状态：small_dummy、large_dummy 都是独立的虚拟头节点，small_tail、large_tail 分别指向它们，cur 指向节点 1。

第一步：cur 是 1，1 < 3，接入小值链。small_tail.next 指向 1，small_tail 变为节点 1，cur 移动到 4。

第二步：cur 是 4，4 >= 3，接入大值链。large_tail.next 指向 4，large_tail 变为节点 4，cur 移动到 3。

第三步：cur 是 3，3 >= 3，接入大值链。large_tail 变为节点 3，cur 移动到 2。

第四步：cur 是 2，2 < 3，接入小值链。small_tail 变为节点 2，cur 移动到 5。

第五步：cur 是 5，5 >= 3，接入大值链。large_tail 变为节点 5，cur 变为 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。这个行为恰好是正确行为：空链表拆分后还是空链表。

但如果你没有用虚拟头节点，而是试图判空后再处理，你可能会多写很多防御代码。用好虚拟头节点后，空链表自动被覆盖。

单节点链表，比如只有一个节点 5，x=3。此时 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_dummy，small_tail.next 最终被设置为 large_dummy.next，也就是大值链的头节点。返回的结果就是整条原链表。这也完全正确。

这一类“极端值分布”用例，我建议你在测试时至少跑一遍。它们往往能暴露你对特殊情况处理的不够谨慎，而且只需要改动构造链表的数据即可，成本非常低。

5.3 重复值节点和逆序输入

重复值节点的情况，比如链表2 -> 2 -> 2，x=2。因为条件判断是cur.val < x，所以三个节点全都走大值链，最终返回的原链表。注意这个行为依赖判断条件的设计。如果你写成cur.val <= x，那小于等于的节点会进小值链，结果完全不同。题目里通常写的是“小于 x 的在前，大于等于 x 的在后”，所以使用<判断才是符合要求的。

逆序输入，比如5 -> 4 -> 3 -> 2 -> 1，x=3。手动过一遍你会发现，小值链最终是 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 指向画出来。

最后再分享一个扩展建议：刷完这道题后，试着不看任何参考，把按奇偶位置拆分和按区间拆分这两个变体也实现一遍。如果这两道也能顺利写对，说明你真的掌握了“链表分流”这一类问题，而不是仅仅背下来了这一个解法。