单链表拆分全解析：思路、代码与边界细节

单链表的拆分这个题目我估计只要是学过数据结构的朋友都跟它打过照面。课程作业里有它期末考试有它技术面试的笔试环节也经常拿它来试探基础功。表面上看就是一个 while 循环加上几个指针操作的事但真正上手写代码的时候你就会发现一会儿链表断了一会儿死循环了一会儿拆完之后两个链表乱成一团。这篇就基于最常见的单链表拆分例题把核心思路、代码写法、边界条件到调试技巧完整梳理一遍尤其是那些你不踩一次坑就根本不会注意到的细节。1. 单链表拆分的核心思路到底在考什么1.1 先看明白题目表面的意思先给不熟悉的读者垫个底。单链表拆分字面意思就是给定一条链表通过调整指针的指向把它拆成两条或者多条链表。听起来很简单对吧其实就是把一条路上的车分成两条路上的车。但难点不在拆这个动作本身而在拆完之后每条链表依然要是一个完整、正确、可遍历的链表不能断、不能丢节点、不能出现环。举个例子。假设原始链表是1 - 2 - 3 - 4 - 5 - NULL按节点位置奇偶拆分后链表A奇数位1 - 3 - 5 - NULL 链表B偶数位2 - 4 - NULL这里有个关键认知拆链表并不是把节点复制出来而是把原有节点重新分配到两条链上总共还是那 5 个节点没有新建任何节点只是改变了它们的 next 指向。这一点特别重要因为很多新手会下意识地 malloc 新节点这是完全错误的方向。1.2 考点拆解指针操作、边界思维、内存意识从教学和面试的角度看单链表拆分这个题目本质上是在考三件事第一指针操作的熟练度。链表的每个节点通过 next 指针串联拆分操作就是不断地修改指针指向这一过程需要你非常清楚每一步改的是哪个节点的 next改完之后谁还指着谁。稍微糊涂一点链表就断了。第二边界条件的意识。空链表怎么办只有一个节点的链表怎么办拆到最后一个节点时它的 next 应该指向哪里这些都是拆分题的核心考点。我见过太多同学主逻辑写对了结果忘了把拆出来的第二条链表的末尾节点指向 NULL导致遍历第二条链表时直接越界。第三内存安全的意识。链表拆分的节点都是原链表上的不需要释放也不需要新建。但某些拆分的变体题目要求原地重排比如把小于某个值的节点放到前面大于的放到后面这时候还要注意不要丢节点、不要形成自环。内存安全意识不仅仅是会不会 free而是你在操作指针时始终清楚每个节点的归属。提示判断一道链表题是不是真的掌握了你就问自己三个问题——每个节点是否都还可达每个链表的尾节点是否都指向 NULL有没有任何节点被意外丢失2. 例题一按节点位置奇偶拆分这是最经典的拆分题也是很多教材和网课里的标准例题。原题通常是这样的给定一个单链表把第 1、3、5...个节点拆出来组成一条新链表剩下的第 2、4、6...个节点留在原来的链表中返回新链表的头指针。2.1 从模拟过程开始理解先别急着写代码先在草稿纸上模拟一遍。原始链表是head - 1 - 2 - 3 - 4 - 5 - NULL第一步节点 1 在奇数位应该去链表 A。第二步节点 2 在偶数位应该留在原链表。第三步节点 3 再去链表 A。第四步节点 4 留在原链表。依此类推。注意这里有一个非常重要的操作顺序问题当你把节点 1 接到链表 A 上时链表 A 的尾节点指针需要指向节点 1但操作完之后你还得能继续访问到节点 2。也就是说在修改节点 1 的 next 之前必须先保存好节点 2 的位置。这就是链表操作的通用原则先保存后继再改指针。这个原则我重复强调多少遍都不为过。链表题里百分之九十的 bug都是因为改指针之前没有保存下一个节点的地址。2.2 C 语言实现双尾指针法下面我给出一种最直观的实现方式维护两个尾部指针 tailA 和 tailB分别指向两条链表的当前末尾。为什么用尾指针因为拆分的过程就是不断地在两条链表的尾部追加节点如果每次都从头遍历找尾节点时间复杂度就变成了 O(n²)完全没有必要。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 拆分函数: 奇数位节点构成 headA, 偶数位节点留在原来的 head 中 Node* splitByPosition(Node *head) { if (head NULL || head-next NULL) { return NULL; // 空链或只有一个节点时没有偶数位节点可拆 } Node *headA NULL; // A 链头(奇数位) Node *tailA NULL; // A 链尾 Node *headB head; // B 链就是原链头不变 Node *tailB head; // B 链尾初始指向第一个节点(节点1) // 注意当前节点要从第2个节点(位置2)开始处理 Node *cur head-next; int pos 2; while (cur ! NULL) { Node *nextNode cur-next; // 核心先保存后继防止断链 if (pos % 2 0) { // 偶数位节点追加到 B 链尾部 tailB-next cur; tailB cur; } else { // 奇数位节点追加到 A 链尾部 if (headA NULL) { headA cur; tailA cur; } else { tailA-next cur; tailA cur; } } cur nextNode; pos; } // 关键两条链的尾节点都要指向 NULL if (tailA ! NULL) tailA-next NULL; tailB-next NULL; // 这里我们把 headA 作为返回值原链 headB 通过外部参数带出 // 为了方便演示我用全局变量或指针参数来返回两个头指针 return headA; }等等上面这个函数有个设计问题它只返回了新链表的头指针那原链表的新头怎么带出去在 C 语言里通常用二级指针或者定义一个结构体把两个头都包起来。下面给出完整可运行的版本。2.3 完整可运行版本我习惯写一个示例程序把整个过程跑通这样既方便验证逻辑也方便调试。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 辅助函数创建新节点 Node* createNode(int data) { Node *n (Node*)malloc(sizeof(Node)); n-data data; n-next NULL; return n; } // 辅助函数尾插法建立链表 void append(Node **head, int data) { Node *n createNode(data); if (*head NULL) { *head n; return; } Node *cur *head; while (cur-next ! NULL) { cur cur-next; } cur-next n; } // 辅助函数打印链表 void printList(Node *head) { Node *cur head; while (cur ! NULL) { printf(%d, cur-data); if (cur-next ! NULL) printf( - ); cur cur-next; } printf( - NULL\n); } // 拆分位置为奇数的节点放入 dst 链表偶数位的留在原链 // 返回新链表的头指针原链表的头通过 srcHead 指针带出 Node* splitByPosition(Node *src, Node **srcHead) { // 处理空表和单节点的情况 if (src NULL) { *srcHead NULL; return NULL; } if (src-next NULL) { *srcHead src; return NULL; } Node *headOdd NULL; // 奇数位节点组成的新链表 Node *tailOdd NULL; Node *headEven src; // 偶数位节点留在原链头还是 src Node *tailEven src; // tailEven 初始指向第 1 个节点(位置 1) Node *cur src-next; // cur 从位置 2 开始 int pos 2; while (cur ! NULL) { Node *next cur-next; // 先保存后继的关键一步 if (pos % 2 1) { // 奇数位 if (headOdd NULL) { headOdd cur; tailOdd cur; } else { tailOdd-next cur; tailOdd cur; } } else { // 偶数位追加到原链尾 tailEven-next cur; tailEven cur; } cur next; pos; } // 收尾两条链的尾节点都必须指向 NULL if (tailOdd ! NULL) tailOdd-next NULL; tailEven-next NULL; *srcHead headEven; return headOdd; } int main() { Node *head NULL; int arr[] {1, 2, 3, 4, 5, 6, 7}; for (int i 0; i 7; i) { append(head, arr[i]); } printf(原始链表: ); printList(head); Node *oddHead splitByPosition(head, head); printf(奇数位链表: ); printList(oddHead); printf(偶数位链表(原链): ); printList(head); return 0; }运行结果原始链表: 1 - 2 - 3 - 4 - 5 - 6 - 7 - NULL 奇数位链表: 3 - 5 - 7 - NULL 偶数位链表(原链): 1 - 2 - 4 - 6 - NULL等一下这个结果不对。奇数位链表应该是 1, 3, 5, 7 才对怎么变成从 3 开始了这里我一定要专门提一下这就是拆分题最容易出现的初始条件错误。我在上面的代码里让 cur 从 src-next即第2个节点开始pos 从 2 开始这意味着我把位置 1 的节点直接留在原链上充当了偶数位链表的头。但按照题目定义位置 1 是奇数位它应该归入奇数位链表。而原链表拆分后偶数位链表的头应该是位置 2 的节点。所以严格按题目定义来正确逻辑应该是第一个节点进入奇数位链表第二个节点进入偶数位链表一路交替分下去。2.4 修正后的正确写法Node* splitByPosition(Node *src, Node **evenHead) { if (src NULL) { *evenHead NULL; return NULL; } Node *headOdd src; // 第1个节点属于奇数位链 Node *tailOdd src; Node *headEven NULL; // 偶数位链暂时为空 Node *tailEven NULL; Node *cur src-next; // 从第2个节点开始 int pos 2; while (cur ! NULL) { Node *next cur-next; // 保存后继 if (pos % 2 0) { // 偶数位节点 - 偶数位链表 if (headEven NULL) { headEven cur; tailEven cur; } else { tailEven-next cur; tailEven cur; } } else { // 奇数位节点 - 奇数位链表 tailOdd-next cur; tailOdd cur; } cur next; pos; } tailOdd-next NULL; if (tailEven ! NULL) tailEven-next NULL; *evenHead headEven; return headOdd; }这下运行结果就对了原始链表: 1 - 2 - 3 - 4 - 5 - 6 - 7 - NULL 奇数位链表: 1 - 3 - 5 - 7 - NULL 偶数位链表: 2 - 4 - 6 - NULL我把这个坑单独拿出来讲是因为它太典型了。很多时候你觉得自己思路很清楚但手一抖就把初始条件设置错了。正确的做法是动手写代码之前先在纸上明确第一号节点归属哪条链再开始写。这个习惯能帮你省掉大把调试时间。2.5 时间复杂度分析这个算法的核心循环只遍历了一次原始链表每次循环执行的操作是常数级别的指针赋值所以时间复杂度是 O(n)其中 n 是链表节点总数。额外空间方面我们没有新申请任何节点只是用了几个指针变量所以空间复杂度是 O(1)。这也是链表拆分题的标准要求不能申请额外空间必须原地拆分。面试官如果看到你 malloc 新节点来复制数据基本就判定这道题不及格了。3. 例题二按数值大小拆分单链表另一个高频例题是按数值拆分。原题通常长这样给定一个链表和一个基准值 x把链表拆成两条或重排为一条——所有小于 x 的节点排在前面大于等于 x 的节点排在后面。3.1 两种考法的区别这个题目有两个变体。变体一是拆成两条链表小于 x 的组成链表 A大于等于 x 的组成链表 B。这个变体本质上跟例题一完全同构区别只是判断条件从位置奇偶变成了data 是否小于 x。变体二是原地重排为一条链表不返回两条链而是要求最终的链表满足所有小于 x 的节点都在大于等于 x 的节点前面并且节点之间的相对顺序保持不变。这其实要求你先把链表拆成两条子链再首尾相接。变体二更常考也更容易出错。我下面重点讲这个。3.2 核心思路拆开再拼接整体思路分三步第一步遍历原始链表把每个节点根据 data 与 x 的比较结果分别尾插到小于链或大于等于链。第二步遍历结束后两条子链的尾节点都需要指向 NULL。第三步把小于链的尾节点接到大于等于链的头节点上。这里有一个非常容易被忽略的边界问题如果所有节点都小于 x那么大于等于链是空的反过来也一样。拼接的时候要判断空链的情况否则调用 NULL-next 直接崩溃。3.3 参考代码实现Node* partitionList(Node *head, int x) { // 使用哑结点简化头指针的处理 Node dummyLess, dummyGreater; dummyLess.next NULL; dummyGreater.next NULL; Node *tailLess dummyLess; Node *tailGreater dummyGreater; Node *cur head; while (cur ! NULL) { Node *next cur-next; // 保存后继 if (cur-data x) { tailLess-next cur; tailLess cur; } else { tailGreater-next cur; tailGreater cur; } cur next; } // 两条链收尾 tailLess-next NULL; tailGreater-next NULL; // 拼接 if (dummyLess.next NULL) { return dummyGreater.next; } if (dummyGreater.next NULL) { return dummyLess.next; } tailLess-next dummyGreater.next; return dummyLess.next; }再看一个具体的运行例子原始链表: 1 - 5 - 3 - 7 - 2 - 8x 4 过程 1 4 - 小于链 5 4 - 大于等于链 3 4 - 小于链 7 4 - 大于等于链 2 4 - 小于链 8 4 - 大于等于链 小于链: 1 - 3 - 2 大于等于链: 5 - 7 - 8 拼接结果: 1 - 3 - 2 - 5 - 7 - 8注意这里的相对顺序是保持的小于链内部是 1、3、2跟原链中它们出现的顺序完全一致。3.4 为什么用哑结点上面代码里我用了 dummyLess 和 dummyGreater 两个哑结点。所谓哑结点就是一个不存储有效数据的头节点它的作用只有一个简化对链表头部的处理。如果不使用哑结点那么在向某条链尾插第一个节点时需要特殊判断这条链是不是空的为空则头指针指向当前节点不为空则尾指针的 next 指向当前节点。这个判断在循环里写起来很啰嗦也容易漏。用哑结点之后不管链是否为空操作都是统一的tailLess-next cur; tailLess cur;这就统一了代码逻辑减少了很多 if 分支。链表题目里头节点变化的情况特别多哑结点这个技巧一定要掌握。我自己的经验是凡是要构建新链表的题目只要允许就优先用哑结点能把出错概率降一个量级。注意哑结点是在栈上分配的局部变量不参与链表数据的存储也不得被 free。只要把它当作一个临时工具用完就扔问题不大。4. 实操中的边界条件与内存安全链表题有个特点主逻辑写对不算什么所有边界条件都扛得住才算真的会了。拆分题更是如此一不小心就是断链或死循环。4.1 空链表与单节点链表空链表head NULL直接返回。很多人的习惯是先写主逻辑再想着补边界我建议反过来先想清楚空的情况再动手写。单节点链表只有一个节点时无论如何拆分结果都是这一条链里有原节点另一条链为空。这时候要注意返回的另一个头指针应该被设置为 NULL而不是一个野指针。为了强化这个意识我在代码里经常写一个前置判断if (head NULL) { *headA NULL; *headB NULL; return; } if (head-next NULL) { *headA head; *headB NULL; return; }4.2 尾节点置空的必要性这是拆分题里最经典的 bug拆完之后某条链的最后一个节点还指向原来在另一条链上的某个节点遍历时形成了意料之外的串联甚至形成环。拿例题一来说假设最后处理的是链表的第 7 个节点它被追加到了奇数位链表它的 next 当时还指向 NULL没问题。但如果最后处理的是第 8 个节点它被追加到偶数位链表可是它原来的 next 可能指向 NULL也可能指向已经被拆走的节点——如果被拆走保留一个陈旧的指针必须手工置空。所以每次拆分循环结束后两条链的尾节点都手动指向 NULL。这个操作看起来是保险起见实际上就是标准流程不能省。4.3 指针保存的顺序先存后继再改指针我在前面反复强调这里用一个小例子彻底说明白。Node *p head; while (p ! NULL) { p p-next; // 错误修改之前没保存下一个节点 }这不是一个完整的例子但它说明了一个普遍问题如果你准备把节点 p 从原链中拆走改 p-next 之前必须先把 p-next 原来的值存下来否则改完后你就再也找不到原来的后继了。正确的写法是Node *q p-next; // 先保存后继 p-next 新目标; // 再修改指针 p q; // 移动到后继这个顺序是链表操作里的铁律没有例外。我见过太多同学在这里栽跟头在循环里先改了 next 再去取下一个节点结果取到的根本不是原来那个后继整个链表就乱了。4.4 内存泄漏的隐患如果拆分过程中丢失了某些节点这些节点既不在链表 A 中也不在链表 B 中那么在完整的程序运行期间它们占据的内存无法被释放这就是内存泄漏。链表题里内存泄漏不一定马上暴露但在长时间运行的程序里是隐患。还有一种情况是试图 free 不该 free 的节点。拆分不释放任何节点所以不要随意调 free。只有当你确定某个节点不再被任何链表引用时才能释放它。在拆分题的标准写法中节点只在链表间转移不释放。5. 常见错误与调试心得这部分我把自己踩过的坑和帮别人调试时见过的典型问题整理一下列成一张速查表方便你自查。5.1 拆完链表之后新链表的头指针不对症状打印结果时第一个节点缺失或者多了一个不该有的节点。排查思路回到拆分循环之前检查初始化时头指针的指向。我自己调试这类代码时习惯在循环里每处理一个节点就打印一次当前状态确认节点进入了正确的链表。等整个流程想清楚了再把打印删掉。5.2 遍历新链表时卡死或无限循环症状输出结果没完没了或者程序卡住不动。排查思路首先检查尾节点是否指向 NULL。如果新链表的某个节点的 next 指向了链表中间的某个节点就会形成环遍历自然停不下来。我在解决这个问题时有个技巧用一个计数器限制遍历次数比如最多打印 100 个节点。一旦超过就说明有环立刻输出来避免程序挂死。定位到有环的节点后向前找谁把 next 指向了这里基本就是拼接或收尾时的遗漏。5.3 修改了原链表但新链表也变了症状打印原链表时发现它少了节点或者顺序不对。排查思路这是正常的因为拆分就是修改原链表。容易出错的是你期望原链表保持某个状态但实际处理过程中改变了它的结构。如果你需要原链表保持不变那必须先拷贝一份节点出来而不是直接改原链。但绝大多数拆分题的预期结果就是原链表被修改所以这不是 bug是理解偏差。5.4 忘记处理空链表导致崩溃症状程序一运行就段错误。排查思路在函数入口先判断 head 是否为 NULL。这几乎是所有链表题的通病解决办法也很简单写代码前先列出空、单节点、双节点、多节点这几种情况逐一确认处理方式。5.5 常见问题速查表现象可能原因排查思路链表断成两截部分节点丢失改指针前没有保存后继检查循环内是否先保存了 next遍历死循环尾节点 next 未置 NULL形成环检查循环后两条链的尾节点收尾新链表第一个节点缺失初始条件设置错误归属判断错误回到循环之前明确首个节点的归属段错误/野指针空链表未处理或使用了未初始化的指针入口处增加空链判断确保所有头指针初始化输出顺序与预期不符链表的拼接顺序写反了检查 tailX-next headY 的赋值方向内存泄漏节点丢失导致无法访问遍历检查每个节点是否可达5.6 我的调试经验调试链表题目我强烈建议你写一个 printList 辅助函数并且在关键节点前后调用它。不要觉得打印代码写起来浪费时间它能直接可视化链表的状态比你在脑子里空想快多了。我调试链表题的习惯是第一步先打印初始链表确认数据正确。第二步每处理完一个节点或一个循环轮次打印当前两条链的状态。第三步确认所有尾节点指向 NULL 后再完整打印最终结果。这种方法听起来笨但真的能解决绝大多数链表 bug。等你熟练了自然会减少打印的频率不过在初学阶段多打印绝对不是坏事。另外如果手头有调试器在可能出错的指针操作处打断点逐步观察每个指针变量的值是更高效率的排查手段。但示意的直观性不如打印所以我通常是先用打印定位大问题再用断点处理细节。6. 说说这道题的实际价值单链表拆分的代码看起来简单但它背后的思维范式在很多复杂场景里都会被复用。第一种场景是快速排序算法在链表上的实现。听过链表快排的朋友应该有印象它本质上就是不断地把链表按基准值拆成小于链和大于等于链再递归处理并拼接。如果拆分逻辑不熟链表快排基本写不出来。第二种场景是 LRU 缓存淘汰机制。LRU 里维护数据访问顺序的链表当某个节点被访问时需要把它移到链表头部这种从中间摘走一个节点再插入到头部的操作本质上也是一次非常微小的链表拆分与拼接。你能安全地把目标节点的前后链接接好比拆分整条链的难度只高不低。第三种场景是操作系统内核、数据库缓冲池里的各种链表管理。嵌入式开发里常见的空闲链表分配器就是从空闲链表里拆出需要的块拆分操作同样会用到。所以别小看这道例题。它培养的是指针操作的直觉和对链表结构的敏感度有了这个底子后面学红黑树、跳表、B 树里那种更复杂的节点指向关系时你会轻松不少。我在实际带人和面试的过程中见过太多候选人能流畅背诵各种排序算法的复杂版本但写一个链表拆分却漏洞百出。这两类能力是不同维度的——一个考验记忆与算法复杂度分析一个考验对基础数据结构的肌肉记忆。后者反而是工作中更常用的底层能力。如果你正在准备面试我的建议是不用刷一堆花哨的难题先把链表相关的经典题目——反转链表、合并有序链表、找中间节点、拆链表——练到闭着眼睛都能写对边界条件再谈其他。这几个题目是链表考点的半壁江山而拆分题恰好把指针修改的顺序、边界判断和哑结点技巧都串在了一起性价比极高。最后分享一个我的个人习惯拿到任何链表题目我不会立刻打开代码编辑器而是先在纸上画出链表的箭头关系用箭头表示 next 的指向变化。一个节点从一条链转移到另一条链画上几笔就看清楚了很多隐藏的边界条件也会自动跳出来。这个习惯帮我在线下手写代码的环节里少犯了很多错你也可以试试。