企业官网建设流程全解析

单链表拆分的题目，在数据结构作业和面试手写题里出现的频率都不低，但很多同学做到这类题时，还是容易卡在“怎么把节点断开再拼到新链上”这一步。实际上，单链表拆分的核心就两件事：第一，搞清楚按什么规则拆；第二，保证拆的过程中不要丢节点、不要成环。只要把这两个点想透了，代码写起来就是顺理成章的事。

这篇文章就围绕“单链表的拆分例题”来展开，从题目本质、常见拆分思路、带头节点与不带头节点的差异，到实操代码和常见坑位，一次性梳理清楚。无论你是正在准备数据结构考试，还是在复习链表相关的手写算法题，这篇文章都可以作为一份可以直接照做的复习笔记。

1. 单链表拆分的本质：到底在拆什么

1.1 拆分的核心逻辑与题目常见问法

链表拆分，本质上就是把一条链表上的节点，按照某个规则重新分配到两条或更多条链表上。最常见的问法有两种：

• 按位置拆分：把第1、3、5...个节点放到A链表，第2、4、6...个节点放到B链表，也就是奇偶位置拆分。
• 按值域拆分：把所有满足某个条件的节点放到A链表，其余放到B链表，比如“小于某个阈值的放一边，大于等于的放另一边”。

这两种拆分方式看起来差别很大，实际代码逻辑高度相似，核心都是遍历原链表，逐个把节点摘下来，挂到目标链表的尾部。关键点在于：每次摘节点时，要先把下一个节点的指针保存下来，否则一旦把当前节点从原链路上摘走，后面的节点就找不到了，链表当场就断了。

我见过不少初学者写拆分代码时，出现“只拆了一个节点，后面的节点全部丢光”的情况，原因就是没有保存后继指针。这个问题在后面演示代码的时候会专门再强调一次。

1.2 为什么拆分题这么常见：考点拆解

链表拆分之所以成为高频考题，是因为它一个题目同时考察了好几个基本功：

第一，考察对链表指针结构的理解。链表节点和节点之间是靠指针串起来的，拆分操作涉及大量指针修改，写错一个就可能导致整个链表断裂或者成环。

第二，考察遍历和摘节点的基本功。拆分要边遍历边摘节点，这比单纯的遍历要难一些，因为遍历过程中链表的形态在不断变化。

第三，考察细节处理能力。比如最后一条链表的尾节点有没有置空、链表原本是空表怎么办、头节点处理是否正确等，这些细节恰恰是评分的关键点。

所以，拆分题其实是一道“一题多考”的综合性题目，会做拆分题，基本上链表这块的核心操作就过了一大半。

2. 拆分题的两种主流思路：原地拆分 vs 新建链表

2.1 思路一：原地拆分，不额外申请节点

所谓原地拆分，就是直接复用原链表上的节点，把这些节点通过修改指针，重新串成两条新链表。这个思路的优势很明显：不需要额外的内存空间，时间复杂度是O(n)，空间复杂度是O(1)。

很多教材和考试题默认要求这种写法，因为这是最省资源的做法。写的时候要注意，虽然它叫“原地拆分”，但你仍然需要两条新链表的头指针，以及各自的尾指针，用来挂接新节点。

我用一个生活化的例子来解释：你有一串珠子，现在要把这串珠子分成两串，一串放红色珠子，一串放蓝色珠子。原地拆分的意思就是，你不去造新的珠子，只是把原来串好的线剪开重新穿，红色珠子串到一根新线上，蓝色珠子串到另一根新线上。整个过程珠子还是那些珠子，只是线的连接关系变了。

2.2 思路二：新建链表，复制节点数据

另一种思路是遍历原链表，每遇到一个符合条件的节点，就新建一个节点，把原节点的数据复制过去。这种写法更直观，但空间复杂度变成O(n)，而且代码更繁琐。

实际用途上，这种写法多见于你“不想破坏原链表结构”的场景，比如你要保留原始数据做多次拆分，或者原链表有其他指针指向它、不能改动。但在考试和面试中，一般不推荐优先选这个方案，因为多申请了O(n)的空间，还会被追问“能优化吗”。

这里还是用珠子的例子：新建链表拆分，相当于你按照原来珠子的颜色，去商店买了一串新珠子串好，原来那串珠子一动不动。这样最安全，但也最费钱。

2.3 为什么推荐原地拆分：空间与可扩展性考虑

从工程实践角度看，原地拆分的优势不只是省空间。很多时候，链表中的节点除了数据域和指针域，还可能携带其他信息，比如缓存频率计数、引用计数等。如果你新建节点，这些额外的信息都得手动复制，一旦遗漏，新链表的数据就是不完整的。而原地拆分直接将原节点挪到新链上，所有附加信息天然保留。

所以，不管是做题还是实际开发，优先掌握原地拆分，都是更划算的选择。

3. 核心实操：带头节点与不带头节点的处理差异

3.1 带头节点的链表拆分：尾插法的标准写法

先明确一下，很多教材里的链表都带有一个不存储实际数据的头节点，这个头节点存在的意义，是让“在链表第一个位置插入节点”和“在其他位置插入节点”的操作逻辑统一。拆分场景下，头节点也让代码写起来更省心，因为你不需要单独讨论“新链表是不是空表”的情况。

带头节点的情况下，两条新链表各自先分配一个头节点，然后遍历原链表，把满足条件的节点依次尾插到对应链表的末尾。尾插法有一句口诀：先接尾，再移尾。也就是先把新节点的地址赋给当前尾节点的next指针，再把尾指针移动到新节点上。

下面是一个按奇偶位置拆分的典型代码，把带头节点的链表A拆成A和B两条链表，A保留原链表顺序，B是逆序。这个是教材里的常见变形题：

typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; LinkList splitByPosition(LinkList &A) { LinkList B = (LinkList)malloc(sizeof(LNode)); B->next = NULL; LinkList ra = A; // 指向A链表的尾节点 LinkList p = A->next; // 遍历指针，从第一个数据节点开始 while (p != NULL) { ra->next = p; // 把当前节点接到A的尾部 ra = p; // ra后移 p = p->next; // 暂存并后移遍历指针 if (p != NULL) { LinkList q = p->next; // 保存后继，防止断开后丢失 p->next = B->next; // 头插法把节点插入B链表头部 B->next = p; p = q; // 继续遍历 } } ra->next = NULL; // 最后把A链表的尾节点置空 return B; }

这个代码里的关键点在于，奇数位置的节点尾插到A，偶数位置的节点头插到B，所以B链表中的顺序和原链表是相反的。代码里每次拿到偶数位置节点p时，先用q保存了p的后继，再把p头插到B中，最后p跳到q继续处理。如果不保存q，p->next被改成B的头节点之后，后续节点就找不到了。

3.2 不带头节点的链表拆分：首节点处理的坑

不带头节点的情况下，两条新链表初始都是空表，没有任何“哨兵”节点。此时如何判断新链表是不是空表，就成了一个必须处理的分支逻辑。

不带头节点的拆分代码如下：

LinkList splitWithoutHead(LinkList A, int x) { LinkList B = NULL; LinkList ra = NULL, rb = NULL; LinkList p = A; while (p != NULL) { LinkList q = p->next; // 先保存后继 if (p->data < x) { // 尾插到A if (ra == NULL) { A = p; ra = p; } else { ra->next = p; ra = p; } } else { // 尾插到B if (rb == NULL) { B = p; rb = p; } else { rb->next = p; rb = p; } } p = q; } if (ra != NULL) ra->next = NULL; if (rb != NULL) rb->next = NULL; return B; }

可以看到，和不带头节点的写法相比，每次尾插前都要判断一下尾指针是否为NULL。这个判断本身不复杂，但初学者特别容易漏掉。漏掉之后就会出现访问空指针的错误，或者新链表的第一、第二个节点之间没连上。

注意：如果题目要求不能改动A链表的头指针，你可以额外定义一个A2指针指向原链表首节点，或者让函数返回两条新链表的头指针，避免修改原指针变量。

3.3 拆分成两条以上链表：扩展思路

有些题目会要求把一条链表拆成三条甚至更多条，比如按数据分到三个区间。思路是完全一致的，只是需要维护更多的头指针和尾指针。每轮循环里，判断当前节点应该归属哪条链表，然后执行对应的尾插操作。

这里可以提速的地方是：当你有多个尾指针时，可以用一个数组来存储，这样代码里就不需要写一堆if-else，而是通过计算下标来决定挂到哪个链表。比如三条链表分别是[0, 10)、[10, 20)、[20, +∞)，那就可以算出区间编号，然后统一走一段追加逻辑。

4. 完整实操：从一个典型题到可运行代码

4.1 题目描述与现场分析

假设我现在拿到这样一道练习题：

设计一个算法，将一个带头节点的单链表A分解为两个带头节点的单链表A和B，使得A链表中只含原表中序号为奇数的节点，B链表中只含原表中序号为偶数的节点，且保持原来的相对顺序。

分析这道题，有几个关键点要抓住：

• 原表A带头节点，所以实际数据节点从A->next开始。
• “保持原来的相对顺序”，说明不能用头插法，因为头插法会导致逆序。A和B都必须用尾插法。
• 由于是奇偶拆分，遍历时可以用一个计数器记录当前是第几个节点，也可以直接利用循环的布尔状态来区分奇偶位置，后者代码更简洁。

4.2 代码实现：保序拆分的完整写法

下面是我写的完整实现，使用尾插法同时构建A和B，保持相对顺序：

LinkList splitKeepOrder(LinkList &A) { LinkList B = (LinkList)malloc(sizeof(LNode)); B->next = NULL; LinkList ra = A; // A 的尾指针，初始指向头节点 LinkList rb = B; // B 的尾指针，初始指向头节点 LinkList p = A->next; // 从第一个数据节点开始遍历 int cnt = 0; // 先把A的头节点next置空，避免后续操作残留旧链 A->next = NULL; while (p != NULL) { LinkList q = p->next; // 先保存后继节点 cnt++; if (cnt % 2 == 1) { // 奇数位置：尾插到A ra->next = p; ra = p; } else { // 偶数位置：尾插到B rb->next = p; rb = p; } p = q; // 移动到原链表的下一个节点 } ra->next = NULL; rb->next = NULL; return B; }

这段代码里，我最开始把A->next置空，这一步很多人会忽略。它的作用是防止原链表的头节点还指向旧的首节点，避免后续链表拼接时出现环。当然，如果你在遍历的过程中已经通过ra把所有数据节点重新串起来了，这一步影响不大，但写上是更稳妥的习惯。

代码中的ra和rb分别充当A和B的尾指针，它们的作用就是让尾插操作的时间复杂度保持在O(1)，而不是每次插入都从头遍历到尾。利用计数器cnt的奇偶性来决定挂到哪条链，这样写的好处是逻辑清晰，也不怕题目改成“序号能被3整除的放A”之类的变体。

4.3 无头节点版本的代码对照

如果题目给的是不带头节点的链表，代码会稍微多几个分支。这里给一个完整的无头节点保序拆分版本，方便你对照着看差异。

void splitNoHead(LinkList A, LinkList *AOut, LinkList *BOut) { LinkList ra = NULL, rb = NULL; LinkList p = A; int cnt = 0; while (p != NULL) { LinkList q = p->next; cnt++; if (cnt % 2 == 1) { if (ra == NULL) { *AOut = p; // 第一个节点，直接作为新链头 ra = p; } else { ra->next = p; ra = p; } } else { if (rb == NULL) { *BOut = p; rb = p; } else { rb->next = p; rb = p; } } p = q; } if (ra != NULL) ra->next = NULL; if (rb != NULL) rb->next = NULL; }

对比一下能发现，无头节点版本的核心逻辑和有头节点版本完全一样，区别只在“第一个节点怎么处理”上。有头节点时，头节点天然充当了哨兵，尾插逻辑不用判断链表是否为空；无头节点时，第一次插入需要把新链表头指针直接指向当前节点，后续插入才走尾插。

4.4 测试与结果验证

写完代码，验证是必不可少的。我习惯用一组简单的数据来跑一遍，检查两个关键点：节点是否全部被分配且没有丢失、A和B链表的顺序是否符合预期。

假设原链表数据依次是 1 → 2 → 3 → 4 → 5。

跑完上面的拆分逻辑后，A链表应该是 1 → 3 → 5，B链表应该是 2 → 4。

手动推一遍，至少有四个地方需要核对：

• 节点5有没有被正确处理，因为它是最后一个奇数位置节点，最容易在循环结束时被丢弃。
• 节点4被摘走后，节点5是否还找得到，这考验的正是“先保存后继”的习惯。
• A链表和B链表尾节点的next是否都置为NULL，否则输出链表时会越界。
• 原链表是否已经变成A链表，也就是A的头节点是否直接指向1。

这四点只要有一处出错，程序跑起来就会出现死循环、段错误或者输出顺序不对。

5. 拆分过程中的常见错误与排查技巧实录

5.1 典型错误一：断链导致后半个链表丢失

这是一个非常典型的错误写法：

while (p != NULL) { ra->next = p; ra = p; p = p->next; // 错误：此时p->next可能已被修改 ... }

问题出在，把p接到ra->next后，如果接下来还要对p->next做修改，那原来的p->next就已经被覆盖了。就算当前没有立刻修改，一旦后续代码执行了p->next = ...，原链表后续节点就全丢了。

解决的办法非常简单：进入循环体时，立刻执行LinkList q = p->next;保存后继，后面所有对p的指针操作都随意，遍历时只用q来推进。

5.2 典型错误二：成环导致死循环

还有一种容易出现的错误，是在拆分的最后忘记把尾节点的next置为NULL，导致新链表的最后一个节点还指着原链表后面的节点。最严重的情况是，如果那个节点又是新链表里的某个节点，链表就形成了环，遍历会无限循环。

排查这种问题有一个笨办法但很有效：写一个打印链表长度的函数，如果长度超过预期就说明有环；或者干脆在关键位置设置断点，逐步查看next指针的指向。

5.3 典型错误三：头插与尾插混用导致顺序反转

有些题目要求保持原有相对顺序，但你用头插法实现，结果顺序反转，整个输出就不对了。这是逻辑层面的错误，不是指针层面的，不太容易通过调试发现，因为链表确实“拆分”好了，只是顺序反了。

这里我的经验是：拿到题先圈出“保持相对顺序”或者“逆序输出”这类字眼，再决定用尾插还是头插。如果题目没有明确说逆序，一般默认保持顺序，用尾插。

5.4 典型错误四：空链表或单节点链表的边界处理

空链表处理起来其实很简单，循环根本不进入，两个链表最终都是空表，只要保证头节点的next置空即可。但单节点链表经常有人出错，因为偶数位置的节点不存在，B链表应该为空，但代码里如果尾插逻辑写得不好，可能出现B头节点指针异常或尾节点未置空的情况。

我的建议是：写完代码后，至少手动测试三种输入——空链表、只有一个节点、只有两个节点。三种边界都能跑通，基本就不会出问题了。

5.5 快速排查清单

为了让你在调试时有章可循，我把拆分类题目最容易出问题的点整理成了一份排查清单：

6. 拆分题目的延伸与变式分析

6.1 从拆分到合并：反向操作的联动理解

拆分和合并经常成对出现。如果你会拆分，那么合并其实就是拆分的逆操作——把两条链表按某种规则交错或按顺序拼回一条链表。

理解了这一点，你就能把两个知识点统一起来。其实它们共用同一套“摘节点、挂节点、移动指针”的方法论。学会一个，另一个自然就能上手。

6.2 按值拆分的应用场景

除了位置拆分，按值拆分在实际中也更常用。比如在一组按时间排序的日志链表里，把耗时超过阈值的请求拆出来单独分析；或者在一个排队链表里，把VIP用户和非VIP用户拆成两个队列。

按值拆分的代码和按位置拆分几乎一样，差别只是判断条件从cnt % 2变成了对数据的比较。前面第3.2小节的代码示例就是一个按值拆分的实现，拆分的阈值是x。

6.3 循环链表的拆分

如果题目给的是一条循环链表，拆分时有一个额外的注意事项：原来的尾节点的next是指向头节点的，在遍历时需要用一个计数器或者判断条件来确定链表是否遍历完，不能简单地判断p是否为NULL。

拆分完成后，两条新链表如果要求也保持循环结构，那么需要把两条新链表的尾节点分别指向各自头节点；如果要求拆成普通链表，就把尾节点的next置NULL即可。

这道题的变形，我在实际做题中遇到的频率不低，重点考察的是对循环链表边界条件的理解。

6.4 双链表的拆分

双链表拆分比单链表复杂一点，因为除了next指针，还有prior指针需要重新连接。核心思路不变，但每拆一个节点，都要同时修改两条链上对应的prior指针，而且要保证不会出现指针悬空或成环。

双链表拆分题目一般出现在课程设计的综合题里，面试手写反而少见。如果你单链表拆分能写得很熟练，双链表无非是多处理一个指针域，不用怕。

7. 拆分类题目的通用解题模板

把各种拆分变体做多了以后，我总结了一个通用的模板步骤，基本上可以套用到绝大多数拆分类题目中。虽然不能覆盖所有极端情况，但作为解题的起点足够用。

第一步，确定边界与结构。确认链表是否带头节点、是否循环链表、拆分后是否要保持相对顺序、是否需要释放原头节点。

第二步，准备新链表骨架。如果有头节点，则分配头节点并置next为空；如果没有头节点，则新链表初始为NULL，同时准备各个尾指针。

第三步，遍历原链表的每个数据节点。进入循环体时，第一行代码永远是保存当前节点的后继指针q，这是整个模板中最关键的一行，能避免绝大多数断链问题。

第四步，按条件把节点挂到目标链表。用尾插法保持顺序，用头插法逆序，挂接时更新对应链表的尾指针。

第五步，循环结束后，将所有新链表的尾节点next置NULL，返回需要的头指针。

第五步虽然简单，但特别容易被忽略。因为尾节点置空属于“最后一步细节”，在写代码时容易被前面复杂的指针操作分散注意力。

8. 实操过程中的个人体会与补充建议

在做拆分类题目的过程中，我最大的体会是：这类题目并不考什么高深算法，它考的就是你对指针的掌控力。链表拆分写得好的人，往往不只是代码熟练，更重要的是脑子里的“指针图”足够清晰。

我自己有一个习惯，遇到任何链表操作题，都会在草稿纸上先画一遍节点和指针的变化过程。尤其是拆分这种涉及多条链表的题目，画图比空想要快得多，而且能有效避免“代码改来改去不知道哪里错了”的困境。

如果你是在准备考试或者面试，我建议你把这篇文章里的每段代码都在本地运行一遍，然后把带头节点、不带头节点、奇偶拆分、按值拆分这四种情况组合出几道变式题来练手。组合方式可以参考：

• 带头节点 + 按位置奇偶拆分 + 保持顺序
• 不带头节点 + 按值大小拆分 + 保持顺序
• 带头节点 + 按位置奇偶拆分 + B逆序
• 不带头节点 + 分割成三条链表

每种组合都写一遍，写多了之后你会发现，这类题换汤不换药，核心逻辑全都在那“保存后继、移动尾指针、尾节点置空”三板斧里。

最后再说一个写这类代码时很实用的小技巧：如果你担心指针改来改去把自己绕晕，可以给代码加上适当的注释，把每条链表的“当前状态”注释出来。比如ra是A链表的尾节点，rb是B链表的尾节点，p是原链表的遍历指针。这样过两天再回头看代码，也能一目了然，不至于重构整个逻辑。

拆分题本身不难，但它值得你花时间把它练透，因为它是链表操作里最能体现基本功的题目之一，练好它，很多链表相关的问题都会迎刃而解。