大小链表法：链表分割的通用解法与指针细节全解-平芜编程栈

很多人在初学链表时，最怕的就是指针绕来绕去，一调试就懵。分割链表其实是一类特别典型的操作题，LeetCode上从“按值划分链表”到“奇偶链表”再到“分隔链表”的变体，核心思想都是同一套——把一条链拆成两条，最后再接回去。今天想聊的“大小链表法”，就是这套思想里最朴素、也最不容易出错的一种实现方式：把小节点串成一条链，大节点串成一条链，完了直接拼接。

这套方法不需要复杂的原地交换，不需要想破头去处理“当前节点到底要不要换位置”，只要你会“往链表尾部挂节点”，就能写得出来。尤其适合笔试、面试里要求快速手写代码的场景，也适合刚学完单链表基本操作、想拿一个真正有含金量的练习题的初学者。我会把拆分思路、指针细节、常见翻车点，以及C、C++、Python、Java的实现都过一遍，最后再聊聊它和逆置链表、循环链表这些“联动玩法”怎么配合。

1. 先搞清楚需求：分割链表到底在拆什么

1.1 一句话理解“大小链表法”

大小链表法这个名字其实很直白：你面对一条原始链表，心里拿某个基准条件（比如节点值是否小于x）把所有节点分成两拨。小于x的放到small链，大于等于x的放到large链，等遍历完原始链表，两条新链也分别串好了，最后只要执行一句 smallTail->next = largeHead->next，一条“按要求分割且保持相对顺序”的新链表就出来了。

举个例子你就秒懂：原链表 1 -> 4 -> 3 -> 2 -> 5 -> 2，基准 x = 3。分割后应该是 1 -> 2 -> 2 -> 4 -> 3 -> 5。注意这里不是排序，不是要你从小到大排好，而是“小于3的保持原来的先后顺序，大于等于3的也保持原来的先后顺序”，最后小链表在前、大链表在后。这种“稳定分割”恰恰是大小链表法最舒服的地方，因为你只是尾插，没有改变节点之间的相对次序。

1.2 为什么用“大小链表”而不是原地交换

有些同学一看到分割，第一反应是原地交换：遍历时遇到一个“大节点”，就想办法把它换到后面去。逻辑上可行，但写起来极其痛苦——你得记录“当前小于区间的终点”，还得考虑连续多个大节点的情况，稍有不慎就丢节点或者成环。更麻烦的是，原地交换通常破坏了稳定性，同样的输入每次跑的相对顺序可能都不一样。

大小链表法的思路是“空间换逻辑”：我只额外使用两个哑结点（dummy node），实际不申请任何新节点，所有节点还是原来那几块内存，只是把它们的 next 指针重新梳理了一遍。时间复杂度 O(n)，空间复杂度 O(1)，性能一点都不差，但代码的可读性和正确性直接上了一个台阶。面试时评委最看重的就是：思路清晰、边界条件处理到位。用大小链表法，你能做到一版过。

1.3 常见变体：奇偶分割、区间分割、循环链表分割

“按值大小分”只是最常见的一种，往深了推，你会发现很多链表题目本质上都是“分割”：

奇偶链表：把下标为奇数的节点串一条链，下标为偶数的串一条链，最后偶数链接在奇数链后面。
区间分割：把链表按某个区间 [low, high] 分成三部分：小于low、在区间内、大于high。
循环链表中的分割：约瑟夫问题、轮转调度等场景里，需要把一个单向循环链表按条件拆成两条子循环链表，核心同样是大小链表法，只是最后要记得让两条新链各自“首尾相接”。

所以学这个方法不是只背一道题，而是拿到了一把处理“链表按条件分流问题”的通用钥匙。这把钥匙的底层，说白了就是链表的遍历 + 尾部插入 + 指针重置这三板斧。

2. 核心细节：链表操作最容易翻车的几个点

2.1 带头结点 vs 不带头结点：别在首节点上栽跟头

很多初学者在纸上画链表时都好好的，一上机就崩，原因基本都出在“头结点”上。

带头结点的链表：链表最前面有一个实际不存储数据的哨兵节点，它的 next 才指向真正的第一个节点。好处是“空表”和“非空表”操作统一，插入删除首节点时不需要特殊分支。很多教材和企业规范都推荐带头结点，嵌入式里更是常见，因为初始化方便，内存管理也相对清晰。

不带头结点的链表：一个指针直接指向第一个数据节点，链表为空时这个指针就是 NULL。这种写法节省一个节点，但插入删除首节点时要额外判断“当前链表是否为空”“要操作的是不是头节点”，代码分支陡然变多。

大小链表法里，最好的做法是每维护一条链，就造一个哑结点当作“临时头结点”。哑结点在分割过程中不存任何数据，只是为了让你统一使用 tail->next = p 这个操作而不用去专门判断“第一个节点怎么挂”。到最后返回结果时，返回 dummy->next 即可。

注意：哑结点不是“带头结点”的链表头，它只是你为了简化逻辑临时构造的辅助节点。函数结束前，记得把两个哑结点释放掉（C/C++里），避免内存泄漏。Python 和 Java 有垃圾回收，不用手动释放，但思想上要知道这两个节点不是最终链表的一部分。

2.2 双链尾与成环检测：分割后链表为什么总会莫名其妙成环

我最常被问到的一个问题是：为什么我照着大小链表法的思路写，跑起来却死循环了？一排查，发现是“成环了”。大小链表法里成环的来源有两个：

大链表尾部没有置空。你遍历完原链表，最后一个节点的 next 可能还指向原链表后面的某个节点（如果你提前 break），或者指向小链表的某个节点，结果拼接后形成环。
分割过程中没有及时把已挂到新链的节点“摘干净”。比如你把节点 p 挂到 small 链尾之后，忘了把 p->next 先压成 NULL，那么原始链表的下一个节点还“惦记着”它，两条链其实还是纠缠在一起的。

所以大小链表法有一条铁律：每次分离一个节点，先把它从原始链表里孤立出来——也就是把这个节点的 next 置空，再挂到新链上。遍历结束后，再单独执行 smallTail->next = largeDummy->next，并且确保 largeTail->next = NULL。

检测成环的简单方法也很实用：你可以用一个快指针和一个慢指针去“跑圈”，快的每次走两步，慢的走一步，如果相遇就是有环。但调试分割链表时我更推荐肉眼检查：打印拼接后链表的每一个地址，看有没有重复地址出现。一旦有重复，说明环已经形成，从那里断开重接。

2.3 指针移动顺序与插入操作：先改链还是先挪指针

链表几乎所有 bug 都来自指针操作顺序。以尾插为例，标准三步是：

保存当前节点的下一个位置nextTemp = p->next，因为马上要破坏 p->next。
把 p 接到目标链尾部：tailSmall->next = p。
更新尾指针：tailSmall = p。
最后一定记得把 p 从原链上“切断”：p->next = NULL。
然后移动遍历指针p = nextTemp，进入下一轮循环。

我见过太多人把第二步和第五步搞反：先把 p 挪到 nextTemp，结果 p 自己丢了；或者先重置 p->next，结果原链表后续遍历直接断掉。记住一个口诀：“先存后接，再接再断，最后前移。”这个顺序在任何链表的插入、分割、归并操作里都通用。

3. 实操过程与核心代码实现

3.1 以C语言为例：最基础的大小链表法

C语言没有C++的引用传递（严格说C++才有引用，但也有很多地方用指针的指针），所以头节点指针经常要传二级指针，或者靠返回值把新头带出来。写分割函数时，我更习惯用返回值返回新链表的头指针，内部用哑结点管理，这样调用方只收一个值就行。

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* partition(struct ListNode* head, int x) { struct ListNode smallDummy, largeDummy; // 哑结点，不动态分配也行 struct ListNode *smallTail = &smallDummy; struct ListNode *largeTail = &largeDummy; smallDummy.next = NULL; largeDummy.next = NULL; struct ListNode *cur = head; while (cur != NULL) { struct ListNode *nextTemp = cur->next; // 先保存后继 if (cur->val < x) { smallTail->next = cur; // 尾插到小链 smallTail = cur; } else { largeTail->next = cur; // 尾插到大链 largeTail = cur; } cur->next = NULL; // 从原链上摘除 cur = nextTemp; // 继续遍历 } smallTail->next = largeDummy.next; // 小链接大链 // 注意：如果 largeTail 还在，需要保证它的 next 是 NULL，上面已经置空了 return smallDummy.next; }

这段代码有几个容易忽视的点：

两个哑结点smallDummy和largeDummy直接在栈上分配，不需要 malloc。因为它们在遍历过程当中只会被“引用”而不会被作为返回结果，返回的是它们的next，所以栈上声明没问题。
我把cur->next = NULL放在cur = nextTemp之前，先切断再前移。如果你先cur = nextTemp，那当前节点就找不到了，没法置空。
最后smallTail->next = largeDummy.next有一个极端情况：如果所有节点都小于 x，则 largeDummy.next 为 NULL，拼接后就是小链自己，完全正确；反之如果所有节点都大于等于 x，那么 smallDummy.next 为 NULL，返回大链，同样正确。

这个函数的时间复杂度是 O(n)，只遍历了一次链表；空间复杂度 O(1)，只用了几个指针变量。

3.2 用C++结构体语法复刻：代码几乎一样，但思路要习惯RAII

C++ 里最标准的链表定义方式和 C 几乎无异，只是多了构造函数：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };

分割函数用 C++ 写，结构上和 C 完全一致，但我会更强调“不要手动管理哑结点生命周期”的写法：尽量在栈上构造哑结点，函数结束后自动回收，不要 new 出来然后 delete，免得漏。

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

如果你们的项目里规定使用智能指针来管理链表节点，比如std::shared_ptr<ListNode>，那思路是一样的，只是访问成员用cur->next时需要注意是否为空指针。个人实践下来，算法题和嵌入式裸机场景里裸指针最顺手，生产环境业务代码里智能指针更安全。但“大小链表法”的核心不依赖内存所有权模型，它只关心指针的指向关系。

3.3 Python实现：简洁但绝不能犯的小白错误

Python 的链表定义通常用类来实现：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = 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: next_temp = cur.next # 先保存后继 if cur.val < x: small_tail.next = cur small_tail = cur else: large_tail.next = cur large_tail = cur cur.next = None # 从原链摘除 cur = next_temp small_tail.next = large_dummy.next return small_dummy.next

Python 新手最容易犯的错就是写cur = cur.next一行，其他什么都不管。这样遍历是可以的，但你修改了原链表里节点的 next 指向，如果再依赖原链表的指针顺序遍历，就全乱了。所以必须养成“先备份 next，再改变当前节点”的习惯。

另外，有人喜欢用 while cur.next is not None 而不是 while cur，这会导致最后一个节点没有处理。在分割链表里，我们恰恰也要处理最后一个节点，所以判断条件是while cur is not None或者while cur。

3.4 Java的“引用即指针”：哑结点技巧的优雅之处

Java 里链表节点是典型的引用类型：

public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }

Java 实现只要注意一点：Java 参数传递是值传递，但引用类型变量传过去后指向同一个对象，所以修改对象的 next 会反映到原链表。函数可以直接返回头节点，不需要像 C 那样靠二级指针。

class Solution { 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 nextTemp = cur.next; if (cur.val < x) { smallTail.next = cur; smallTail = cur; } else { largeTail.next = cur; largeTail = cur; } cur.next = null; cur = nextTemp; } smallTail.next = largeDummy.next; return smallDummy.next; } }

Java 面试中特别关注的点是：会不会写出没有意义的空判断？比如if (smallTail == null)这种。在小链表法里，因为有哑结点，smallTail永远不为 null，不需要判空。这就是哑结点技巧最大的价值——让“空表”变成“普通状态”，让所有分支都可以统一处理。

4. 常见问题与排查技巧实录

4.1 问题1：分割完链表成了环，怎么办

现象：函数返回后，你尝试遍历输出链表，结果程序卡死或者打印出无限重复的节点。

排查步骤：

先确认 large 链的尾节点 next 是否为 NULL。最稳妥的做法是在拼接前显式执行largeTail->next = nullptr。
检查遍历原链表时是否每次循环都执行了cur->next = nullptr。如果某个节点没有断开，它可能还指向原链中的下一个节点或新链中的某个节点，两者一交织就成了环。
检验法：弗洛伊德判圈算法（快慢指针）不只用于竞赛，调试链表面试题时也是神器。写一个hasCycle函数，传入返回值，如果返回 true，马上二分定位问题节点。

我调试时习惯再打印每个节点的地址和值，一般出错在“最后一个节点上”，因为循环结束后容易忘记把大链尾置空。

4.2 问题2：内存泄漏和节点丢失

C/C++ 里如果你用 malloc 或 new 动态创建了哑结点，又忘了释放，每次调用 partition 都会漏一小块内存。虽然 8 字节看着无伤大雅，但嵌入式环境或长时间运行的 daemon 里，泄漏会膨胀成大问题。

两条建议：

在栈上声明哑结点（像上面的 C 代码），根本不用考虑释放。
如果必须动态创建，那么返回函数前用free(smallDummy)和free(largeDummy)（C），或用delete smallDummy（C++），但要保证dummy->next已经被保存下来作为返回值。

节点丢失则往往是断链时机不对。比如你先执行smallTail->next = cur，然后忘掉cur->next = NULL，紧接着cur = cur->next，这个时候 cur 已经被接到小链末尾了，cur->next 指向的是原链的下一个节点，所以不会死循环，但你会在新链里意外断开原链的指针顺序，导致后面的节点全找不到了。这也是调试时“只输出了前几个节点就停”的常见原因。

4.3 问题3：递归 vs 迭代，什么时候用哪种

大小链表法无论用哪种语言，我都推荐迭代。理由很简单：

递归实现链表分割时，每层递归调用都多一个栈帧，链表过长（几万节点）时，C/C++ 默认栈空间很可能不够，直接爆栈。
迭代只需要 O(1) 的额外空间，且代码逻辑平铺直叙，不会因为“返回到底该接谁”而烧脑。
面试场景下，迭代版更不容易暴露递归出口写错的尴尬。

递归并非一无是处，比如逆置链表（反转单链表）时递归写法非常优雅，递归出口就是“空或只有一个节点直接返回”，然后层与层之间反转 next 指向。但那是另一个场景，分割这件事，迭代始终优先。

4.4 常见问题速查表

问题现象	根本原因	解决方法
死循环	大链尾未置空，或原链节点未断开	每次尾插后置空`cur->next`，拼接前置空`largeTail->next`
输出少了后半段	尾插时忘了保存`nextTemp`，导致后续节点丢失	循环第一行先保存`nextTemp = cur->next`
首节点丢失	没有用哑结点，插入首节点时分支写错	统一使用哑结点，返回`dummy.next`
全部节点分成两段但顺序乱了	把分割做成了排序，或者尾插顺序错误	只尾插，不修改节点值，保持相对顺序
内存泄漏	动态哑结点没释放	用栈上哑结点或函数结束前释放
Java的引用指向没生效	用`smallTail = cur`后又修改了`cur.next`，导致 tail 跟着变	记住`tail`变量保存的是“当前尾节点”，而不是尾节点的前驱

5. 从基础到实战：大小链表法的扩展玩法

5.1 与单链表逆序结合：反转后分割再合并

反转单链表（逆置链表）是链表考点的另一个大哥。如果遇到“先按大小分割，再把每段各自逆序”这种组合题，最好的办法是拆开写，不要试图在一个循环里同时完成两个操作。

组合题的经典套路：

第一遍遍历，统计链表长度或者根据条件确定分割点。
用大小链表法把链表拆成两条子链。
对两条子链分别写一个reverse函数，返回新的子链头。
最后按题目要求拼接（可能是小链逆序后接大链，也可能两头都逆序）。

reverse函数就是链表操作里最经典的“头插法”：

struct ListNode* reverse(struct ListNode* head) { struct ListNode* prev = NULL; struct ListNode* cur = head; while (cur != NULL) { struct ListNode* nextTemp = cur->next; cur->next = prev; prev = cur; cur = nextTemp; } return prev; }

分割之后再做反转，每段步长是 O(m) + O(n)，总体依旧是 O(n)。这样写的好处是每个函数都只做一件事，边界条件好验证，面试时也不容易临场胡掉。

5.2 循环链表中的分割：环形结构下怎么判空

单纯循环链表（带头结点的循环单链表）在操作系统的任务队列、内存管理空闲块链表里经常出现。分割循环链表比单链表多一个麻烦：遍历的终止条件不是cur == NULL，而是cur == head（回到了起点）。

以“带头结点的循环单链表”为例，你要按值 x 拆成两个循环链表，套路是：

先确定原链表非空：head->next == head表示空表（只有头结点自己指向自己）。
遍历时以cur != head作为循环条件。
分割完成后，需要手动让小链的尾节点重新指向小链的哑结点（形成循环），大链同理。
最后小链和大链都各自成环，不会自动接回 head。

这里特别强调：循环链表的尽头不是 NULL，如果照搬上面的单链表代码，会因为访问NULL->next直接段错误。所以凡是涉及循环链表，先检查判空条件，再决定循环体里cur是否可能走到 dummy 上。

5.3 嵌入式场景：无头结点链表的资源约束

嵌入式里常用“不带头结点的单链表”，因为每一个节点都要省，头结点在嵌入式里被认为是浪费。嵌入式链表代码的特点是：节点通常是一个结构体的成员（叫做内嵌链表节点），而不是单单一个 next 指针；内存来自静态数组或内存池，不允许 malloc。

在这种场景下用大小链表法，有几个调整：

不需要额外创建哑结点？建议还是创建，但可以直接用一个struct ListNode dummy的局部变量。嵌入式情况下栈空间很宝贵，所以 16 字节的哑结点也可能要精打细算。替代方案是：分割前先单独处理首节点，之后循环中所有插入都保证“目标链非空”，从而统一头插或尾插逻辑。
不允许动态分配内存正好符合大小链表法的特点——它根本不需要新节点，只改变指针方向，非常适合内存池分配的内存块。
无头结点加尾插时，每次插入都要判空，代码要多写几行，但把“哑结点”的思想移植过来就舒服了：你可以在 stack 上构造一个虚拟局部变量当哑结点，照样统一逻辑，结束只返回它的 next。嵌入式 C 编译器的优化通常能把这个栈上哑结点优化进寄存器，实际占用几乎为零。

5.4 单链表基本操作实验课：为什么建议先用纸笔

如果你是在做单链表的基本操作实验或者刚学数据结构，我不建议直接打开编译器敲代码。链表全部的奥义都在指针之间的拓扑关系，而这些关系的调试在屏幕上远不如在纸上直观。

我的建议流程：

在纸上画一条至少 8 个节点的链表，标清每个节点的地址（用 A、B、C…代替）。
给定 x 的值，手动模拟大小链表法的每一步，把每一步操作后的 next 指向画出来。
特别注意：当小链尾指向当前节点后，原链表从当前节点开始就“断了”，那怎么继续遍历？这就是为什么必须先保存 nextTemp。
等手推两遍不出错，再上机。代码能一遍编译通过的概率会大幅提高。

这个“先纸笔，后键盘”的方法，对链表遍历、链表插入、链表逆序、循环链表判空这些基础实验都适用。很多自己觉得“逻辑没毛病但程序跑不起来”的同学，回头去纸上推一遍，几乎都能自己发现问题出在哪一步。

我个人在实际操作中体会最深的一点是：大小链表法不像快排的原地划分那样需要精巧的交换逻辑，它本质上是“空间换烧脑”——不申请节点、只多几个指针，却把难度降了一个量级。面试时不管遇到按值分割、奇偶分割还是区间分割，我都先写两个哑结点，剩下的就是机械尾插。另外，如果你是非科班转码的初学者，建议把今天的例子分别用 C 和 Python 各写一遍，然后自己再改写成逆序链表的版本，彻底吃透“保存后继、改指向、前移”这三板斧。链表这关过了，后面的树和图都会顺很多。