企业官网建设流程全解析

分割链表这道题，在 LeetCode 上是第 86 题。很多人第一次看到它，觉得无非是把链表按某个值切两半，但真动起手来，能一次写对的人并不多。网上讨论最多的解法，就是今天要拆开讲的大小链表法——也叫双哑节点法，或者分离拼接法。这个方法的价值不只是解一道题，它背后是一整套链表“按条件拆链、再合并”的通用套路。无论你是刚刷链表题的新手，还是准备面试想把这题讲清楚的候选人，这篇文章都值得看完。我会从题目本质、核心原理、代码细节、边界测试到扩展题目，把每个环节都过一遍。

1. 一道看似基础却让很多人翻车的链表题：分割链表到底在考什么

1.1 题面看起来只有一句话

题目描述很简单：给你一个单链表的头节点head和一个整数x，把所有小于x的节点放到所有大于等于x的节点之前，同时要求节点之间的相对顺序保持不变。

举个例子。原链表是：

1 -> 4 -> 3 -> 2 -> 5 -> 2，x = 3

期望结果是：

1 -> 2 -> 2 -> 4 -> 3 -> 5

注意一点：等于x的节点，比如这里的3，不属于“小于 x”的那一拨，它要去后半段。很多人写代码时会把等于x的节点算到前半段，这就不符合题意了。这题的分类口径是“严格小于”和“大于等于”，没有中间地带。

题目要求的“保持相对顺序”是另一个容易被忽略的点。也就是说，在前半段里，1必须在两个2前面，因为原链表里1就在2前面；在后半段里，4必须在3和5前面，因为原链表里它们的顺序就是4 -> 3 -> 5。这个约束直接影响了解法选择。

1.2 真正考的不是“划分”，而是“稳定划分”

如果你刷过数组版的快速排序，或者做过荷兰国旗问题，第一反应可能是：这不就是拿x做一次 partition 吗？

但数组的 partition 可以靠交换元素实现。比如[1, 4, 3, 2, 5, 2]按3划分，交换完之后可能变成[1, 2, 2, 4, 3, 5]，虽然结果一样，但数组本身的元素顺序已经被打乱了，只是我们只关心值的分类，不关心元素身份。

链表题不一样。链表节点是带“身份”的，你不能简单地把节点里的 value 换掉，因为节点之间通过next指针连接。面试官想看到的是：你能不能让这些节点重新串起来，并且保持原来的相对次序。这个“稳定”的要求，直接把交换法排除了。

所以这道题真正的考点有三个：

• 能不能想出“拆成两条链再合并”的思路；
• 会不会用哑节点处理新链表头部不确定的问题；
• 能不能处理好指针修改的顺序，避免丢链和成环。

这三个点，每一个都在大小链表法的实现里有对应细节。

1.3 我见过的最常见的错误解法

刷题群里经常有人分享这题的“奇怪解法”，我总结一下最常见的三种。

第一种：把链表转成数组，在数组里 partition，再重新建链表。结果是对的，但空间复杂度到了 O(n)，而且完全没有操作链表指针，等于放弃了这题想考察的核心能力。面试的时候这么写，面试官大概率会追问“能不能不用额外空间”，然后你就得重写。

第二种：原地扫描，每遇到一个大于等于x的节点，就把它移到链表末尾。这个思路听起来可行，实际写起来非常容易出错。你需要在移动时同时维护前驱节点、尾节点和遍历指针，而且还要防止把已经移到后面的节点再扫一遍，稍不留神就是死循环。我见过有人在这里写完代码，自己都说不清cur在某一轮之后到底指向哪里。

第三种：直接对节点值重排。先遍历链表把所有 value 收进一个列表，排序或分组后再回填到原节点。这种做法既破坏了原链表结构的意义，也没有锻炼到指针操作，属于“为了通过而通过”。

这些错误解法的共同问题，是没有抓住题目的本质：这是一个要求稳定顺序的链表重排问题，最自然的做法，就是把每个节点“摘下来”，按条件追加到两条新链的尾部，最后再把两条新链接起来。这就是大小链表法的核心思想。

2. 大小链表法的核心拆解：两条子链 + 一次遍历

2.1 先理解“大小链表法”这个名字

所谓“大小链表法”，就是把原链表拆成两条子链：一条放所有小于x的节点，叫 small 链；一条放所有大于等于x的节点，叫 large 链。遍历原链表一遍，把每个节点分别追加到对应子链的尾部，最后让 small 链的尾节点指向 large 链的头部，返回 small 链头部即可。

这个方法还有两个别名：双哑节点法、分离拼接法。名字不同，说的是同一件事。叫“双哑节点法”是因为实现时通常会为两条子链各建一个哑节点，用来处理新链表头部为空的情况；叫“分离拼接法”则更强调操作过程——先分离，再拼接。

用生活里的例子类比：你手里有一列队伍，现在要求按身高分成两队，矮的在前，高的在后，并且队伍内部的先后顺序不能变。最高效的方式不是让队员互相换位置，而是你从队头开始，一个个把人领走：个子矮的站到 A 队队尾，其余站到 B 队队尾。等全部领完，让 A 队队尾的人牵住 B 队队头的人，整件事就完成了。

这个过程，和大小链表法的代码是一一对应的。

2.2 哑节点解决“新链第一个元素”的问题

写链表题时，最难处理的往往不是中间过程，而是边界：新链表的头节点到底是谁？

在本题里，原链表的头节点可能是< x的，也可能是>= x的。如果直接用head作为某条链的头，你会发现代码里到处都是 if 判断：这条链现在是不是空的？第一个节点该不该特殊处理？

哑节点就是用来消灭这种分支的。

具体做法是分别创建smallDummy和largeDummy两个占位节点，它们的next一开始都是空。在遍历过程中，所有< x的节点都往smallDummy后面追加，所有>= x的节点都往largeDummy后面追加。因为smallDummy和largeDummy本身永远存在，所以无论子链有没有真实节点，我们都能无脑执行“让尾节点的 next 指向当前节点”。

最后的结果链表头，就是smallDummy.next。如果 small 链一个节点都没有，那smallDummy.next就是空，正好对应“所有节点都大于等于 x”的边界情况；如果有节点，smallDummy.next就是第一个小于 x 的节点，也就是结果链表的真正头节点。

哑节点在这里相当于给链表加了一个“假头”，它不参与最后的结果，但让所有插入操作都变成统一的尾插法，极大地简化了代码逻辑。

2.3 遍历过程：四个指针的配合

大小链表法在遍历过程中会用到四个关键指针：

• smallDummy：small 链的哑节点，固定不动；
• largeDummy：large 链的哑节点，固定不动；
• smallTail：指向 small 链当前的最后一个真实节点；
• largeTail：指向 large 链当前的最后一个真实节点。

为什么需要 tail 指针？因为链表只能从头节点开始向后访问，如果每次追加节点都要临时找“当前链的尾部”，时间复杂度就成了 O(n²)。只要额外维护一个尾指针，每次追加就是 O(1)。

整个遍历过程用伪代码写出来是这样：

smallDummy = ListNode(0) largeDummy = ListNode(0) smallTail = smallDummy largeTail = largeDummy cur = head while cur: nxt = cur.next if cur.val < x: smallTail.next = cur smallTail = cur else: largeTail.next = cur largeTail = cur cur = nxt largeTail.next = null smallTail.next = largeDummy.next return smallDummy.next

每次循环里，先把cur.next保存到nxt，再把cur追加到对应链的尾部，然后更新尾指针，最后让cur回到原链表的下一个节点。

这里有一个容易想不明白的地方：把cur追加到新链尾部后，cur.next还指向原链表的下一个节点，这没关系吗？

没关系。因为我们在下一轮会继续处理nxt，而cur已经被新链的尾指针“接管”了。它的next会在后续操作中被覆盖，或者到最后统一处理。所以没必要在循环里手动把cur.next置空，那样反而会丢掉还没遍历的后继节点。

2.4 最后一步拼接：为什么 largeTail.next 必须为 null

这是大小链表法最容易被忽略的一步，也是面试官最喜欢追问的点。

先看不做这一步会怎样。假设原链表是：

1 -> 4 -> 2 -> 3 -> 0，x = 3

按大小链表法遍历：

• 1 < 3，进 small 链，small 链变为1；
• 4 >= 3，进 large 链，large 链变为4；
• 2 < 3，进 small 链，small 链变为1 -> 2；
• 3 >= 3，进 large 链，large 链变为4 -> 3；
• 0 < 3，进 small 链，small 链变为1 -> 2 -> 0。

注意，遍历结束时，large 链的尾节点是3，而3的next还保留着原链表中的指向，也就是节点0。可0已经被放进 small 链了。

如果此时直接执行smallTail.next = largeDummy.next，得到的结果是：

1 -> 2 -> 0 -> 4 -> 3 -> 0 -> 4 -> 3 -> ...

链表成环了。

原因在于 large 链的尾节点没有断尾，它仍然指向一个已经被接到 small 链的节点。所以正确的做法是，在拼接之前，先执行largeTail.next = null，把 large 链的尾巴彻底断开。这也是为什么很多人说这题的代码“最后一行是灵魂”。

smallTail.next = largeDummy.next这行本身也有讲究。要接的是 large 链的第一个真实节点，也就是largeDummy.next。如果 large 链为空，largeDummy.next是 null，那么 small 链的尾部会被置空，这也正好防止 small 链尾部遗留任何旧指针。

3. 代码落地的关键细节：什么时候保存 next，为什么最后必须断尾

3.1 参考实现：Python 与 C++ 版本

先看 Python 实现，代码很紧凑：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 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: if cur.val < x: small_tail.next = cur small_tail = small_tail.next else: large_tail.next = cur large_tail = large_tail.next cur = cur.next large_tail.next = None small_tail.next = large_dummy.next return small_dummy.next

再看 C++ 版本，我用的是栈上的哑节点，避免手动 new 和 delete：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} }; ListNode* partition(ListNode* head, int x) { ListNode smallDummy(0); ListNode largeDummy(0); ListNode *smallTail = &smallDummy; ListNode *largeTail = &largeDummy; ListNode *cur = head; while (cur) { if (cur->val < x) { smallTail->next = cur; smallTail = cur; } else { largeTail->next = cur; largeTail = cur; } cur = cur->next; } largeTail->next = nullptr; smallTail->next = largeDummy.next; return smallDummy.next; }

两个版本逻辑完全一致。C++ 版本里用栈对象ListNode smallDummy(0)和ListNode largeDummy(0)，可以避免内存泄漏问题，同时也不影响返回结果，因为我们返回的只是smallDummy.next，不涉及哑节点本身。

3.2 两种写法的差异：要不要先保存 nxt

在 Python 版本里，我直接写了cur = cur.next，没有先把cur.next存到临时变量。很多读者会问：这安全吗？

答案是：在当前这个实现里安全，因为我们在循环体里没有显式修改cur.next。small_tail.next = cur和large_tail.next = cur修改的是当前链尾节点的next，而不是cur这个节点的next。所以cur进入下一轮循环时，它的next还指向原链表中的后继节点。

但这里有一个风险：如果以后你在这个循环体里加了一行cur.next = None，或者你想提前把当前节点“摘下”，那cur.next就丢了，后面的链表全部找不回来。为了避免这种隐患，很多经验丰富的程序员会习惯性地先保存后继：

while cur: nxt = cur.next if cur.val < x: small_tail.next = cur small_tail = cur else: large_tail.next = cur large_tail = cur cur = nxt

这个版本更防御性。尤其当你在面试时紧张，手一滑写错某个指针，有nxt兜底，至少不会把整个链表遍历断掉。我个人推荐在工程项目里用带nxt的版本，面试讲题时也可以用这种写法，顺便告诉面试官：“我先保存下一个节点，防止指针修改影响遍历。”

3.3 断尾动作的微观验证

在 2.4 节里，我们已经见识了不断尾导致的成环问题。这里再进一步拆解，为什么large_tail.next = None能同时解决两类情况。

情况一：large 链为空。比如所有节点都小于x，那么large_tail还是large_dummy，large_dummy.next是 null。此时执行large_tail.next = None不会影响任何节点，然后small_tail.next = large_dummy.next会把 small 链尾部置空，正好符合“后半段没有节点”的预期。

情况二：large 链不为空，且最后一个 large 节点的原后继已经进入 small 链。这就是成环的场景。large_tail.next = None强行切断了最后一个 large 节点与旧链表之间的残留连接，等 small 链末尾接上 large 链头时，整条链表就是一条干净的线性链。

情况三：large 链不为空，且最后一个 large 节点本来就是原链表尾节点，它的 next 本来就是 null。这时large_tail.next = None无非是重复赋值，没副作用。

所以large_tail.next = None是一个“无副作用但必须有”的保险操作。少了它，代码可能在大部分测试用例下都能跑通，但会挂在那些“原链表最后一个节点属于 small 链”的用例上。

3.4 复杂度分析和一个容易误判的地方

时间上，每个节点只被访问一次，所以时间复杂度是 O(n)。即使做了拆链、拼接、断尾，也都是常数级别的操作，不会增加整体复杂度。

空间上，除输入链表本身外，只用了两个哑节点和几个指针，因此空间复杂度是 O(1)。

很多人会把“空间复杂度 O(1)”误解为“不能创建任何新节点”。其实哑节点属于辅助节点，数量固定，不随输入规模增长，所以仍然算 O(1)。同样，如果你用 vector 或 list 保存节点再重建，那额外空间是 O(n)，不够好。

这里也顺便回答一个高频追问：题目要求“原地”处理时，大小链表法算不算原地？算。因为节点对象本身就是原链表的节点，我们没有新建任何真实数据节点，只修改了节点之间的next指向，属于原地重排。

4. 边界条件与测试用例：拿到面试官面前自证正确性

4.1 空链表与单节点

先看最简单的边界。

空链表：head = None，直接返回None。用代码走一遍，cur一开始就是 null，循环不执行，large_tail.next = None后，small_tail.next = large_dummy.next就是把small_dummy.next赋值为 null，返回 null。完全正确。

单节点链表，根据head.val和x的关系，有三种情况：

单节点场景下，无论它进哪条链，断尾和拼接的逻辑都成立。

4.2 所有节点都小于 x

输入：[1, 2, 3]，x = 4

遍历之后，small 链为1 -> 2 -> 3，large 链为空。此时large_tail还是large_dummy，large_dummy.next是 null。执行large_tail.next = None没有破坏任何链表；执行small_tail.next = large_dummy.next等价于3.next = null。

这一步很关键。如果不做拼接，或者拼接逻辑写错，3.next可能还指向旧链表中的残留内容。这个用例正好测试了“当 large 链为空时，small 链尾巴必须被清空”。

4.3 所有节点都大于等于 x

输入：[4, 5, 6]，x = 3

遍历后 small 链为空，large 链为4 -> 5 -> 6。此时small_tail仍然等于small_dummy。执行small_tail.next = large_dummy.next，其实是把small_dummy.next指向4，然后返回small_dummy.next，也就是节点4。

这个用例有意思的地方在于：拼接那行代码不仅负责“小链尾接大链头”，还在 small 链为空时承担了“设置返回头”的职责。如果代码里没有这行拼接，或者你试图针对 small 链为空单独写一个分支，反而容易画蛇添足。

4.4 重复值和 x 不存在于链表中

重复值场景，比如[2, 2, 2]，x = 2。所有节点都大于等于 2，全部进 large 链，原顺序保持为2 -> 2 -> 2。这里再验证一点：等于 x 的节点和大于 x 的节点在 large 链内部的相对顺序不会被打乱，就是原链表的顺序。

再看[7, 7, 2, 9]，x = 7。其中2 < 7，进 small 链；两个 7 和 9 都进 large 链，且保持原顺序。结果是2 -> 7 -> 7 -> 9。等于 x 的节点仍然待在后半段，没有跑前面。

x 不存在于链表中但大小关系存在，比如[1, 4, 6, 3]，x = 5。小于 5 的是1, 4, 3，大于等于 5 的是6，同时保持各自顺序，结果是1 -> 4 -> 3 -> 6。注意这里 3 原本在 6 后面，现在因为小于 5 被移到前面，但它在 small 链内部的顺序跟在原链表中的相对顺序一致，仍然是 1、4、3 这个次序。

把这些边界用例整理出来，其实也是在面试时向面试官展示代码健壮性的好方法。讲完思路和实现，顺手列几个用例走一遍，会显得你对这题的理解非常完整。

5. 从分割链表到一类题：大小链表法的扩展套路

5.1 链表快速排序的 partition 阶段

如果你熟悉快速排序，应该知道数组快排的核心是 partition：选定一个基准值，把小于基准值的放左边，大于等于基准值的放右边。链表虽然不能随机访问，但 partition 的思想一样能用，只是实现方式要从“交换元素”变成“拆链合并”。

大小链表法就是链表版 partition 的天然实现：把基准值当作 x，遍历一遍链表，小于 x 的进 small 链，大于等于 x 的进 large 链，再合并。这个过程是稳定的，不会像数组交换法那样打乱相等元素的顺序。如果你要手写链表快排，partition 阶段直接套用这个方法，比在链表上用双指针交换要简洁得多。

5.2 三路分区：小于 x / 等于 x / 大于 x 的扩展

有时候面试官会追问：如果要求把链表分成三段，小于 x 的在前，等于 x 的在中，大于 x 的在后，怎么做？

大小链表法稍加扩展即可。准备三个哑节点：smallDummy、equalDummy、largeDummy，再准备三个尾指针。遍历原链表时，根据节点的值和 x 的关系，分别追加到三条链的尾部。最后依次拼接：

smallTail.next = equalDummy.next equalTail.next = largeDummy.next largeTail.next = null return smallDummy.next

这里有一个要注意的细节：拼接顺序是 small 接 equal，equal 接 large。中间如果 equal 链为空，equalDummy.next就是 null，那么 small 链尾部会直接指向 null，之后再接 large 链？这里顺序要仔细。正确的写法是先处理 small 和 equal 的拼接，再让 equalTail 接 large 链。如果 equal 链为空，equalTail就等于equalDummy，那么smallTail.next = equalDummy.next = null之后，再执行equalTail.next = largeDummy.next，等价于equalDummy.next = largeDummy.next，这样 small 链尾部依然是 null，没有接上 large 链。所以更稳妥的写法是：

smallTail.next = equalDummy.next if equalTail is not equalDummy: equalTail.next = largeDummy.next else: smallTail.next = largeDummy.next largeTail.next = null

这个问题恰好说明，扩展套路时最容易翻车的不是拆链，而是拼接时空链的处理。面试时如果被追问到三路分区，能主动指出这个边界，会加分不少。

5.3 奇偶链表（LeetCode 328）的同源关系

LeetCode 328 题要求把链表的奇数位节点和偶数位节点分别串在一起，最后偶数位链跟在奇数位链后面。比如1 -> 2 -> 3 -> 4 -> 5变成1 -> 3 -> 5 -> 2 -> 4。

这题的标准解法之一，就是两个哑节点加两个尾指针：遍历链表，第一个节点进 odd 链，第二个节点进 even 链，交替往复，最后拼接。这和大小链表法在结构上完全一致，区别只是判断条件从val < x变成了“当前是奇数位还是偶数位”。

所以当你掌握了大小链表法之后，再看奇偶链表、链表按节点值正负分区、按节点值奇偶分区这类题目，思路都是统一的：确定一个分类规则，用多个哑节点把链表拆开，最后按规则合并。这就是所谓的“一类题”。

5.4 这个套路的适用边界

不过大小链表法也不是万能的。它的前提是：题目允许创建哑节点，且空间复杂度要求是 O(1) 级别的辅助空间。绝大多数链表题都满足这个条件，但如果题目明确要求“不能开辟任何额外节点”，包括哑节点也不行，那大小链表法就不适用了。

另外，它只适用于单链表。双向链表有前驱指针，可以用更灵活的方式做部分反转和移动，但那是另一个话题了。

还有一个容易忽略的限制：大小链表法要求我们能够从头到尾遍历整条链表，所以原链表必须是完整的、无环的。如果输入链表本身带环，这个方法在遍历时就会死循环。当然，链表题通常默认输入无环，真遇到带环输入，需要先做环检测。

6. 我踩过的坑和给刷题人的实操建议

6.1 一次实际的 debug：成环之后怎么定位

我第一次做这题时，写完代码提交，LeetCode 直接给我报了个“cycle detected”。当时第一反应是 while 循环写错了，觉得可能是 cur 指针没有前进，导致无限循环。

后来我在本地调试，把链表节点的地址和 next 指向打出来，才发现问题根本不在循环：遍历早就结束了，是拼接之后的结果链表内部出现了环。具体就是我在 2.4 节里演示的那个场景：large 链的尾节点没有断尾，它的 next 还指向早就被放进 small 链的节点，合并后绕成一个圈。

那次调试让我养成了一个习惯：所有涉及“拆两条链再合并”的链表题，写完代码后先检查三条链的尾节点。哪三条？small 链尾、large 链尾、以及拼接后的整体链表尾。断尾操作一旦缺失，不可能靠调循环条件解决，必须从指针指向上去找原因。

6.2 画图是最快的解题方式

链表题最忌讳上来就写代码。我自己刷题的经验是，先在纸上画出两个哑节点和两条子链的演变过程。每处理一个节点，就画出当前 small 链和 large 链分别是什么样子。尤其是 tail 指针的移动，画两遍之后就不会再犯低级错误。

有一个很小的细节值得单独提一下：更新尾指针时，small_tail = cur和small_tail = small_tail.next在这里是等价的，因为cur正好是刚被追加到链尾的节点。但如果你用的是“先把尾指针的 next 指向 cur，再让尾指针走一步”，两种写法都会让small_tail指向新节点。很多人在这里会纠结，其实没区别，选一种顺手的保持一致即可。真正容易错的是写成small_tail = small_tail.next.next，那就跳到奇怪的位置去了。

6.3 面试中的表达与追问应对

面试时如果让我讲这题，我会按这个顺序讲：

先说原题里的约束：要求保持相对顺序，所以不能交换节点，应该拆链合并。然后说核心结构：两个哑节点，两个尾指针，一次遍历。接着说关键的收尾动作：large 链尾必须断尾，防止成环；small 链尾接 large 链头，返回 small 链头。最后主动给出边界用例：空链表、全小、全大、重复值，各自会得到什么结果。

面试官通常会追问几个问题：

“能不能一次遍历完成？”能。我们的主循环就是一次遍历。

“空间复杂度是多少？”O(1)，哑节点是常数级辅助空间。

“如果等于 x 的节点也要单独分组怎么办？”扩展成三段式，但要小心空链拼接。

“如果 x 不在链表里呢？”不受影响，它只是一个阈值，判断条件永远是用 val 和 x 比较，不需要 x 真实存在。

“如果链表很长，你会担心递归吗？”这题不需要递归，是纯迭代。

这些问题都不难，前提是你真的理解每一步指针在做什么，而不是背答案。

6.4 关于写代码前先画图的最后一点心得

如果只让我给刷链表题的人一句建议，我会说：先把图画清楚，再写代码。

链表题有一个共同特点——代码量通常很小，难的从来不是语法，而是指针之间的托管关系。大小的判定、哑节点的作用、尾指针的更新、断尾的时机，这些东西全部想清楚之后，写出来的代码几乎是“一遍过”。

分割链表这题，是我觉得最适合练习“拆链合并”套路的入门题。它不像反转链表那样有大量指针翻转，也不像合并链表那样只是单调地比较，它需要你同时处理分类、拆分和合并三个动作。把这题吃透，再去做奇偶链表、链表快排 partition、三路分区，你会觉得整个思路一下子通透了。