1. 分割链表这道题到底在考什么我有段时间给校招生做技术面试链表考题里出现频率最高的除了反转链表恐怕就是分割链表了。题目本身长得挺朴素给你一个链表头指针和一个基准值x要求把链表中所有小于x的节点排在所有大于等于x的节点之前同时每个分区内的节点相对顺序不能变。比如原链表是1 - 4 - 3 - 2 - 5 - 2基准值是3结果就应该是1 - 2 - 2 - 4 - 3 - 5。大小链表法就是解决这道题最经典、也最不容易出错的一种思路不用在原链表上左挪右插而是把整条链表看作一串可以自由拆装的节点准备两个新链表一个专门收集小于x的节点另一个专门收集大于等于x的节点最后把两个链表首尾相接完成分割。整个过程只在原链表上做指针搬运不需要额外分配新的节点内存所以时间复杂度是O(n)额外空间是O(1)。这题适合谁来学只要是正在准备算法面试的、刚学完链表想找几个经典题目练手的、或者在写底层代码时需要处理动态节点分流的同学都值得把这道题彻底吃透。因为它表面上是个算法题实际上考的是你对链表指针模型的理解拆链、改链、接链、断链每一个动作都直指指针操作的底层基本功。我见过不少人在这个题上翻车而且翻车的姿势很统一链表拆着拆着就断开了或者拆完之后出现了环。问题往往不在思路而在实现时的顺序和边界处理。所以这篇文章不打算只丢个标准答案给你而是把每个设计决策、每个指针操作的因果关系都摊开讲明白。1.1 题目本身和大小链表法这个名字先把这个题目的训练价值说透。这个题在力扣上叫 Partition List编号 86。很多教材和博客也把它归到链表双指针或链表拆分一类。题目里面有两个关键约束决定了你不能随便写第一不能改变节点内部的val意思是只能调整节点之间的next指针不能去把节点的值取出来重新排序再塞回去。为什么要这样因为链表节点的价值不只是val在真实系统里节点可能携带大量数据或者被别的结构引用搬数据等于把整个节点销毁重建效率和安全性都不可接受。算法题这么约束也是在模拟真实场景。第二两段区间内的相对顺序必须保持。也就是说原链表里排在小值前面的节点分割后在小值区间里仍然排在前面。这个约束淘汰掉了所有交换值的简单思路逼你用指针操作去搬节点。大小链表法这个名字其实是民间叫法形容的是它的核心结构把一条大链拆成一条小值链和一条大值链最后再缝合。思路可以概括成一句话用两个尾指针持续追加遍历一次原链该去小队的去小队该去大队的去大队。我实际面试中观察到一个规律凡是能画清楚这张拆分图的候选人代码基本一遍过凡是上来就想在原链表上就地插入的多半会写出一堆边界判断。原因很简单原链就地插入需要同时维护前驱指针、当前指针、插入位置指针而且分割点两边的插入方向还不一样复杂度全堆在脑子上了。1.2 为什么明明能拆开却总写错三个隐藏难点很多同学看完题说这不就遍历一遍遇到小的连到 small 链遇到大的连到 large 链最后接起来吗道理确实就是这个道理但写代码时总会碰到三个隐藏难点。第一个难点是两个子链表初始都是空的空链表的头节点怎么表示如果你给两个子链表分别定义一个结构体指针然后初始化为NULL那你每次追加节点都要先判断是不是第一个节点是就初始化头不是就接在末尾。写出来就是一大坨 if-else而且很容易漏掉维护尾指针的动作。第二个难点是追加节点时你只是把当前节点从原链捡出来接到新链末尾但原链的遍历指针接下来要怎么走如果先改了当前节点的next再去取下一个节点那原链就断了。顺序必须反着来先把next指针备份到临时变量再把当前节点接进新链最后让遍历指针移动到备份位置。第三个难点是两个子链表最终拼接时大值链的尾部可能还连着一串原来的后继节点如果你不把它的next置空拼接出来的链表就可能变成一个环。很多人在这里栽跟头测试时看似跑通了回头一压力测试就死循环。这三个难点恰恰就是大小链表法比就地插入高明的地方它用两个哨兵节点天然解决了第一个难点用备份 next 再搬运当前节点的固定动作解决第二个难点用一次收尾断链解决第三个难点。思路的逻辑链条是一环扣一环的。2. 大小链表法的三个关键设计现在进入核心原理部分。我不按代码顺序讲而是按为什么要这么设计来讲。理解了这三个设计你就能在面试时跟面试官把思路讲得清清楚楚而不是背代码。2.1 哨兵节点给两个子链表各配一个虚拟头先讲哨兵节点也叫哑节点、dummy node。它的实质是提前申请一个val无效、next为空的临时节点用它当作子链表的虚拟头真正的数据节点都从虚拟头后面开始挂。为什么要多此一举因为空链表没有头节点而不带头节点的链表在做追加操作时必须判断当前链表是否为空为空则设置头指针否则遍历到尾部再连接。这个判断本身不难但它在每次循环里都要执行一遍而且很容易出错。常见的 bug 就是第一个节点加进来了头指向它第二个节点加进来时却忘更新尾指针结果链表只剩最后一个节点。使用哨兵节点后代码变成固定维护一个尾指针初始时尾指针指向哨兵节点以后每追加一个节点就tail-next new_node; tail new_node;。这行代码不管链表是不是空都能用不需要任何条件分支。链表为空时新节点接在哨兵后面哨兵显然是尾节点链表非空时新节点接在真正的当前尾节点后面再更新尾指针。你会发现头这个变量从头到尾只需要读一次。这也呼应了链表题的一个通用经验不确定头在哪、头会不会变时就造一个哨兵。反转链表、合并两个有序链表、删除倒数第 N 个节点全部可以用这个套路把边界问题吞掉。在我写 C 语言版本时还会用一个技巧在栈上直接声明哨兵节点而不是用malloc申请结构体再取地址。比如struct ListNode head;然后struct ListNode *tail head;。这样做的原因是我们根本不需要释放这两个哨兵节点因为它们不是动态分配的函数返回后自动销毁。如果申请堆内存那就必须在返回前记得释放这儿正好省了一步也杜绝了内存泄漏的隐患。2.2 尾插法让小于 x 的节点自然排到前面第二个设计是尾插法。什么叫尾插法就是每次都把新节点追加到链表末尾。这里有个很容易踩的思维误区我必须专门拎出来说一下。很多初学者看到分割两个字第一反应是往中间插或者往头部插。往头部插的问题特别明显头插法会倒序。你按顺序遍历原链时先遇到的、在序列里靠前的节点会被插到链表的更后面最后得到的结果顺序完全反了。题目明确要求相对顺序不变所以头插法一开始就被排除了。尾插法天然满足相对顺序遍历原链的时候你看到的节点顺序就是它们在原链中的顺序尾插法逐个接到末尾新进的永远排在最后先来后到顺序保住了。这里还要强调一下为什么我们敢直接把原链上的一个节点搬到子链表的末尾因为链表操作的本质是把节点从一条链上解下来、挂到另一条链上。只要你还保留着原链剩余部分的入口解下来的节点就跟原来的链没有任何关联了。真正的精髓在于你解节点的时候不要断掉后续路径。这就是下一个设计里要解决的备份 next问题。尾插法配合哨兵节点的代码核心操作可以提炼成一个非常固定的模式tail-next cur; tail tail-next;这两行代码在遍历循环里会出现两次一次是小于x的分支里往 small 链追加一次是大于等于x的分支里往 large 链追加。看起来机械但机械反而好因为你要维护的状态变少了出错的概率自然降低了。2.3 收尾断链防环操作不能省第三个设计是拼接前的收尾断链。这一步在标准解法里通常只有一行largeTail-next NULL;为什么必须要有这行因为 large 链的最后一个节点是从原链上搬过来的它原本的next指针还指向原链上的某个后续节点。如果不把它的next断掉等你执行smallTail-next largeHead-next把两条子链表拼起来之后整个链表就会沿着这个残留的指针绕回原来的链上形成一个环。我这么说可能还是有点抽象用一个具体例子来演示。假设原链是1 - 4 - 3 - 2 - 5基准值x 3。遍历结束后small 链是1 - 2large 链是4 - 3 - 5。注意 large 链的这个5它原本在原链中是最后一个节点next本来就是NULL所以这一例子碰巧断了。但假如原链是1 - 4 - 3 - 2遍历结束时 large 链是4 - 3而节点3的next还指向原链上的2。也就是说 large 链的实际结构是4 - 3 - 2虽然从 large 的视角看尾指针是3但它后面还拖着一截影子链表。你再把smallTail-next指向 large 链的头节点4整体就成了1 - 2 - 4 - 3 - 2 - 4 - 3 ...的死循环。这类问题在调试时特别讨厌链表如果是在打印输出时进入死循环经常表现为程序卡住、内存不断增长甚至直接崩溃。光靠看代码很难一眼找出症结。所以我的习惯是只要在这种从原链拆节点拼新链的算法里动了next指针就老老实实在最后把两条子链的尾节点都断干净。多写一行smallTail-next NULL也不亏还能防一手小的链表恰好为空时悬空指针的问题。提醒一下如果分割后 small 链为空那么smallTail还指向哨兵节点此时把smallTail-next指向largeHead-next没问题因为哨兵节点的next本来就是NULL。真正的风险永远在 large 链尾部因为它的节点来自原链断没断干净完全取决于运气。3. 完整实现C语言版本一步步走原理讲完现在上代码。我选 C 语言当主版本因为指针操作最直观能让你看到每一步到底改了谁的内存。很多语言封装了引用反而掩盖了细节。等你看懂 C 版本的每一步我会给出 Python 和 Java 版本你会发现它们逻辑完全一致只是语法不同。3.1 先看整体代码骨架这个解法建立在标准的单链表结构体上。如果面试时题目没给结构体定义先自己写一个struct ListNode { int val; struct ListNode *next; };然后核心函数如下struct ListNode* partition(struct ListNode* head, int x) { // 在栈上定义两个哨兵节点分别作为小值链和大值链的虚拟头 struct ListNode smallHead; struct ListNode largeHead; smallHead.next NULL; largeHead.next NULL; // 两个尾指针分别指向两条子链表的当前末尾 struct ListNode *smallTail smallHead; struct ListNode *largeTail largeHead; // 遍历原链表 struct ListNode *cur head; while (cur ! NULL) { // 备份下一个节点 struct ListNode *nextNode cur-next; if (cur-val x) { // 接到小值链末尾 smallTail-next cur; smallTail cur; } else { // 接到大值链末尾 largeTail-next cur; largeTail cur; } // 移动到原链表的下一个节点 cur nextNode; } // 防止成环 largeTail-next NULL; smallTail-next NULL; // 拼接小值链的尾部接大值链的第一个真实节点 smallTail-next largeHead.next; // 返回小值链哨兵节点的 next return smallHead.next; }逐行说几个关键点。struct ListNode smallHead;不是在堆上申请而是在栈上声明。这样不用 malloc也不用 free函数结束自动回收绝对不会泄漏。你要是在partition函数里malloc两个哨兵节点又忘了释放程序跑几次内存就上去了在嵌入式环境或长时间运行的服务里这是要命的。smallTail-next cur; smallTail cur;这组操作的意思是把当前节点接到链尾然后把尾指针移动到这个新节点上。这里顺序不能反先接后移。如果先smallTail cur再把smallTail-next cur那smallTail-next就指向了自己直接成环。这种自环 bug 在链表中特别隐蔽print 的时候只会看到同一个节点无限循环。备份nextNode为什么必须做因为一旦执行了smallTail-next cur当前节点的next就被改写了。如果不提前备份你等下执行cur cur-next的时候拿到的不再是原链的下一个节点而是刚挂到小值链上的某个节点。最坏情况下cur会直接回到已经处理过的节点陷入死循环。所以先备份再拆链后移动这个顺序不管在哪个题目里都要刻进肌肉记忆。largeTail-next NULL; smallTail-next NULL;是双保险。largeTail-next NULL是为了断掉原链残留smallTail-next NULL是为了防止 small 链恰好为空时smallTail还指向哨兵而哨兵的next虽然初始化时是NULL但如果你代码中途改过它就不一定了。为了一致性两条链的尾节点都断干净一是防空指针二是防止尾节点恰好是原链某个有残留 next 的节点时出现问题。代码多两行不亏。3.2 用一个例子把指针变化捋一遍只看代码容易飘我拿1 - 4 - 3 - 2 - 5、x 3完整走一遍你对照着想象指针的移动过程。初始状态cur指向1。1小于3把1接进小值链。此时小值链为1smallTail指向1。大值链为空largeTail指向哨兵。cur移动到4。4大于等于3把4接进大值链。小值链不变1。大值链为4largeTail指向4。cur移动到3。3大于等于3接进大值链。大值链变成4 - 3largeTail指向3。注意此时节点3的next还指向原链的2但没关系我们备份过nextNodecur可以正常走到2。cur移动到2。2小于3接进小值链。小值链变成1 - 2smallTail指向2。cur移动到5。5大于等于3接进大值链。大值链变成4 - 3 - 5largeTail指向5。cur移动到NULL循环结束。此时我们还没有做断链和拼接所以从内存的实际结构看大值链的5后面虽然是NULL但4的next指向33的next指向2——而2已经在小值链上了这就是残留指针的典型表现。如果现在直接把小值链尾巴接大值链头2会跟着大值链残留的next把整个结构绕回去形成1 - 2 - 4 - 3 - 2 - 4 - 3...的死循环。所以执行largeTail-next NULL后大值链内部变成4 - 3 - 5 - NULL干净了。最后smallTail-next largeHead.next也就是把2的next指向4得到1 - 2 - 4 - 3 - 5。完美。这个走查过程我建议每个人都亲手在纸上画一遍。面试时如果你能一边画这个图一边给面试官解释当前节点被搬走之前先让临时变量记下它的 next这样原链才不会断面试官立刻就知道你是真的懂链表而不是背答案。3.3 Python和Java的实现差异C语言版本吃透了其他语言就是皮囊问题。Python 的链表节点通常写成class ListNode: def __init__(self, val0, nextNone): self.val val self.next next对应的partition函数def partition(head: ListNode, x: int) - ListNode: small_dummy ListNode() large_dummy ListNode() small_tail small_dummy large_tail large_dummy cur head while cur: nxt cur.next if cur.val x: small_tail.next cur small_tail small_tail.next else: large_tail.next cur large_tail large_tail.next cur nxt large_tail.next None small_tail.next large_dummy.next return small_dummy.nextPython 版本几乎一比一平移。唯一要提醒的是Python 的赋值语句small_tail small_tail.next只是让局部变量指向下一个节点不会影响链表结构所以不需要像 C 语言那样特别小心结构体复制问题。但正因为 Python 屏蔽了指针细节很多人反而容易犯逻辑顺序错误——比如忘了备份cur.next。在 Python 里删掉nxt cur.next这行程序同样会进入死循环只是表现更诡异没有段错误而是程序卡死。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 nextNode cur.next; if (cur.val x) { smallTail.next cur; smallTail smallTail.next; } else { largeTail.next cur; largeTail largeTail.next; } cur nextNode; } largeTail.next null; smallTail.next largeDummy.next; return smallDummy.next; }Java 和 C 几乎没有区别只是把 C 的malloc换成了new。平时用 Java 写算法题的同学如果 C 看不懂直接看 Java 就行思路完全一致。能在三种语言里自由切换地描述同一种解法本身就是一种很好的基本功检验。4. 实战中踩过的坑和排查思路写代码最怕的不是不会而是会了但总在隐藏的小地方翻车。这道题的坑其实非常集中我根据自己刷题和帮人 review 代码的经验把最典型的几个整理出来每个都附上排查思路。4.1 链表成环最典型的翻车现场成环是这个题目翻车的第一大原因而且最隐蔽。我见过不下五个候选人写出成环代码后一脸困惑地说我逻辑没问题啊。请看这段看似正确的代码struct ListNode* partition(struct ListNode* head, int x) { struct ListNode smallHead, largeHead; smallHead.next largeHead.next NULL; struct ListNode *st smallHead, *lt largeHead; while (head) { if (head-val x) { st-next head; st st-next; } else { lt-next head; lt lt-next; } head head-next; } st-next largeHead.next; return smallHead.next; }缺了什么备份head-next。head head-next这行在 else 分支里执行时如果head刚被接到 large 链上其next已经被lt lt-next顺带改过了吗并没有因为lt-next head改的是lt指向节点的next不是head自己的next。真正的问题是当某次循环执行head-val x为真并把head接到 small 链上之后st-next head这个操作修改了head的next吗答案是修改了某个节点的 next而这个节点就是原来的st指向的节点不是head自己。所以head-next在这个场景下其实还是保留着原链的下一个节点那么head head-next暂时没出问题。那为什么一定要备份因为在复杂场景下可能出现head自己恰好就是某个节点的next目标而那个节点已经被提前修改过的场景。更常见的问题是这道题中如果你忽略了断尾拼接后形成环。比如上面的代码最后没有lt-next NULL那么当 large 链尾节点的原始next不是NULL时最终链表就会成环。所以排查思路很简单先不拼接只输出两条子链看它们各自是否正确、是否出现环。如果两条子链都正确再检查拼接处。通常漏掉备份和漏掉断尾两个问题会叠加出现解决掉断尾之间输出子链就能快速定位是哪一步出岔子。排查死循环的一个实用技巧给链表输出限定最大长度。比如循环 100 次就强制停止然后打印当前节点地址和值。看到重复节点地址就说明环在那附近。这个技巧在笔试环境里特别有用因为在线编辑器经常超时不报错误只会给你一个 Time Limit Exceeded你得主动找问题。4.2 头节点处理为什么不能裸指针遍历改值第二个高频 bug 是试图原地修改不拆成两个新链而是在原链表上做插入。有些同学会这样想先找第一个大于等于x的位置然后后面每遇到小于x的节点就把它摘下来插到这个位置前面。听上去很合理但实现时你面临的问题包括如果从头节点开始就小于x那第一个大于等于 x 的位置在哪个节点前面如果所有节点都小于x插在哪如果x极小所有节点都大于等于 x那这段逻辑就退化成空操作没问题但遇到中间状态时维护插入点前驱指针和遍历指针之间的关系非常痛苦。你每移动一次插入点前驱指针就要跟着更新一次稍不留神就会把链拆坏。我见过一个候选人写这个版本面试时对着草稿纸画了十分钟才把第一个节点的特殊处理理清楚最后代码还是错的。这就是典型的不画图就写代码的代价。如果你非要用原地插入法我建议也别硬写。站在工程的角度链表本来就不适合频繁随机插入每插入一次要 O(1) 找位置没错但要同时维护多个指针状态bug 率远高于两个子链法的线性追加。面试官更看重的是稳定可读的解法而不是炫技。所以老老实实用哨兵节点法。4.3 边界条件自测清单我每次写完链表题会默默过一遍下面的边界清单觉得没问题才提交。这里也分享出来第一空链表。head为NULL时两个哨兵节点存在但smallTail指向哨兵largeTail指向哨兵。循环不执行拼接时smallTail-next largeHead.next此时largeHead.next是NULL返回NULL正确。第二所有节点都小于x。此时 large 链为空。断尾时largeTail-next NULL没问题因为哨兵的 next 本来就是 NULL。拼接时smallTail-next largeHead.next而largeHead.next是NULL所以最终返回的就是完整的小值链正确。第三所有节点都大于等于x。此时 small 链为空。断尾、拼接之后返回smallHead.next NULL丢掉了所有节点。等等这里就有问题了题目要求所有节点都大于等于x时应该直接返回整条原链。但这套算法是不是把节点全搬到了 large 链最后返回 small 链的 next结果是空嗯这个问题值得停下来仔细想想。其实不会丢因为smallHead.next指向的是NULL但你执行smallTail-next largeHead.next后smallHead 的 next 就被改成 large 链的头了。换句话说虽然smallTail指向哨兵但哨兵的 next 已被赋值为 largeHead.next所以返回的 smallHead.next 指向 large 链的第一个节点是正确的。第四链表只有两个节点且第一个小于x、第二个大于等于x。这是最基本的正常路径但容易在断尾时出错。第二个节点是 large 尾它的 next 本来就是 NULL所以不断尾也没事但多写无害。第五链表只有两个节点第一个大于等于x、第二个小于x。这种情况下small 链只有第二个节点large 链只有第一个节点。断尾后smallTail-next 指向 secondlargeHead.next 指向 first拼完是second - first。这里正确顺序应该是小于在前、大于在后所以结果是second - first没问题。第六有重复值。这个我不细说了按照小于和大于等于的两个分支重复值是稳定分配在同一个区的代码天然处理。把这些 case 列成一张清单每次写完代码照着走一遍不需要真的跑测试也能发现大部分逻辑漏洞。我刷题时这个清单救了我很多次。5. 这个套路还能延伸到哪里分割链表这道题只是大小链表法这套思路的一个典型应用场。实际工作中同样的思想到处都能看到。5.1 变体题目奇偶链表、三路分割、k组反转先说话算法题层面的延伸。最直接的一个变体是奇偶链表给定一个链表把奇数位节点排在前面偶数位节点排在后面要求保持相对顺序。这个题在力扣上是 328 题解法几乎和分割链表一模一样创建两个哨兵节点odd 链和 even 链遍历一遍按位序号奇偶分流最后拼接。区别只在于分流条件是cur在第几个位置而不是val和x比较。你掌握了大小链表法这道题就是换了个判断条件。第二个变体是三路分割给一个链表和一个x要求小于x的在前等于x的在中大于x的在后。思路直接从两个子链扩展成三个子链three 个哨兵节点三个尾指针最后多次拼接。代码变长了些但结构完全一样。面试遇到这种扩展题你只要说我把大小两路扩展成三路即可面试官会眼前一亮。第三个变体是按某个规则分组成 k 个链表比如先按 hash 值分桶再用这同一个套路逐个分流。这个在算法竞赛题里见过本质就是把二路分流推广成多路分流。关于 k 组反转我多说一句它和大小链表法不是一回事它考的是原地反转 k 个一组但你如果用哨兵节点的思路统一处理头节点变化会发现哨兵思想在这里同样能降低边界复杂度。5.2 工业场景中的分割-分流思想算法题从来不是孤岛。大小链表法在工程里的投影我至少能想到三个场景。第一个是内存池或缓冲区的分桶管理。有一类系统把空闲内存块按大小分成 small 和 large 两个队列分配时从小队找找不到再去大队拆。新回收的内存块按大小塞进对应队列。这个“遍历回收块列表按大小挂到不同队列最后重新组织链表”的过程和分割链表干的活是完全一样的连“断尾防环”这种细节都会出现因为回收块之间如果出现过借用链表的尾部就可能有残留连接必须重置。第二个是任务调度里的多级队列。在嵌入式实时系统或网络协议栈中数据包常被按优先级或长度分类送入不同队列。底层如果不用数组而用链式队列分类转发就是一个多路分割操作。把新到达的任务从输入链表摘下按优先级挂到对应的队列尾最后各队列独立处理。这里同样需要备份 next 节点、更新尾指针、防止残留指针。第三个是消息中间件的主题分区或负载均衡轮转。消费者从上游拿到一批消息根据 key 的哈希值分发到不同分区本质上是把一个逻辑链表按规则拆成多条子链。虽然这些系统通常用数组存队列但链式的思路仍然适用尤其在嵌入式 C 语言实现的分布式组件中。每次我讲完这个题总有人问这题是不是太简单了值得花这么多篇幅讲吗我的回答是越简单的数据结构题越能暴露一个人对指针、边界、动态内存的敏感度。能把拆链、断尾、拼接的每一步都说清楚的工程师写起网络协议处理、操作系统驱动、嵌入式链表池这种代码基础一定是扎实的。我个人实际刷题的习惯是拿到这类题先不急着敲代码先画一张链表图标出哪些节点要被搬走、搬完之后原链的入口在哪、两端的尾巴是谁。画完图代码基本就出来了。这个方法不只在分割链表上有用凡是复杂的链表题画图都是一种极好的解耦方式。你下次再遇到莫名其妙的死循环或者丢失节点先回退到草稿纸十有八九能定位问题。