大小链表法：链表分割的通用解法与指针细节全解-北京尧图网络

很多人在初学链表时最怕的就是指针绕来绕去一调试就懵。分割链表其实是一类特别典型的操作题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结构体语法复刻代码几乎一样但思路要习惯RAIIC 里最标准的链表定义方式和 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_ptrListNode那思路是一样的只是访问成员用cur-next时需要注意是否为空指针。个人实践下来算法题和嵌入式裸机场景里裸指针最顺手生产环境业务代码里智能指针更安全。但“大小链表法”的核心不依赖内存所有权模型它只关心指针的指向关系。3.3 Python实现简洁但绝不能犯的小白错误Python 的链表定义通常用类来实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 版的大小链表法非常简洁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.nextPython 新手最容易犯的错就是写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 smallDummyC但要保证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 各写一遍然后自己再改写成逆序链表的版本彻底吃透“保存后继、改指向、前移”这三板斧。链表这关过了后面的树和图都会顺很多。

大小链表法：链表分割的通用解法与指针细节全解

相关推荐

DRV8818+PIC18F57Q43工业级双极步进电机驱动方案

IS-Fusion复现全指南：多模态3D目标检测环境搭建与训练实战

航空订票系统课设：数据结构选型与核心实现完整方案

更多资讯

modded-nanogpt Speedrun 151.5s 新纪录：删除首个注意力层、扩展验证窗口与 iteration_extension 调度参数解析

git-extras 的 git-rename-remote：无视名称冲突重命名 Git Remote 并即时输出验证

Vibe Coding 幻觉与死循环排查实战：ai-guide 中让失控 AI 重回正轨的完整方法

Sunshine 游戏串流主机 6 步上手指南：从安装到 Moonlight 串出画面

猫抓：三步搞定网页视频下载的浏览器资源嗅探扩展

20 分钟装好 IOPaint：CPU 就能跑的免费 AI 消除工具

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？