链表分段：切分、重组与边界处理实战指南

你有没有遇到过这种场景：一条很长的链表摆在面前，业务要求每隔几个节点取一组处理，或者把所有符合某个条件的节点全部挪到链的前半部分。链表分段（List Section）就是专门处理这类问题的操作。它不是在删除节点，也不等价于全链排序，而是把线性结构按规则做一次“切割 + 重组”，让节点进入不同的逻辑段。数据分页、流式处理、任务切片、缓存分块，底层经常能看到这个思路的影子。这篇文章适合正在啃数据结构的学生、准备算法面试的开发者，以及手头要自己封装链表工具的人。我按实操习惯把从思路到实现再到排查的过程完整走一遍，里面有可以直接复用的代码，也有我踩过之后才明白的坑。

1. 先把“分段”这个词拆清楚：它到底在解决什么问题

链表分段不是一个新算法，而是一族操作的统称。很多人一上来就直接写代码，结果经常在“断开”和“重接”的细节里绕晕。我建议动手之前先想清楚：到底想要什么结果。

1.1 三个典型场景让分段需求落地

第一个场景是数据分页。假设某个模块从底层接口拿到的是单链表结构，前端要按每页 N 条展示。数组可以靠下标 O(1) 定位页首，单链表不行，必须从头顺着 next 指针数到第 N 个节点，然后在段与段之间打标记。这个“数 N 个节点并切一刀”的动作就是分段。

第二个场景是并发任务切片。比如要对百万级任务做批量处理，一次打包 N 个任务交个工作线程。单链表是最简单的 FIFO 队列实现，出队时把链表头部连续摘 N 个节点，当成一批任务下发。摘下来的这一批节点就是一个段，剩下的链是另一个段。

第三个场景是缓存分块。有些本地缓存为了实现分片淘汰策略，需要把一个 LRU 链表按访问频次分成“热段”和“冷段”，调整时只操作段边界，不扫全链。这种场景下分段不是临时的拆分，而是一种持续存在的结构组织方式。

1.2 分段操作的两类模式：切分与重组

同样是“分段”，底层逻辑差别很大。第一类是切分，也就是把一个链表拆成多个独立链表。例如把一条长度为 10 的链按每 3 个节点一组切，得到 3 条长为 3 的链和 1 条长为 1 的链。切分之后，每段都有自己的 head，段之间互不相连。

第二类是重组，也叫类分区操作。节点本身的归属没有改变，但整个链的顺序被重新排列，比如把所有小于阈值 x 的节点放到大于等于 x 的节点前面。从结果看，链表被分成了两个连续的区域，但物理上还是一条链。这种“逻辑分段、物理不断”的操作在实际库里比暴力切分更常用，因为不需要维护多套 head，也更容易保持接口不变。

区分这两类模式很重要。切分要处理“一棵树变多棵树”的指针接续问题，重组则要处理“两块区域拼接”时的首尾衔接问题。很多人把这两者混着写，最后代码逻辑拧成一团。

1.3 为什么说分段的难点全在“边界”

单链表的本质是“一条道走到黑”，每个节点只有 next 一个出口。分段时一旦断开某个 next，后面的整段链在旧引用的世界里就“消失”了。所以所有操作的核心原则只有一条：修改指针前，先把当前位置的上下文记录下来。

具体来说，操作一个待分段区域时通常需要四类指针：前驱 pre，指向前一段的末尾；起点 start，指向当前段的第一个节点；终点 end，指向当前段的最后一个节点；后继 after，指向当前段的下一个节点。start 和 end 框出当前段的范围，pre 和 after 负责把当前段从原链上“摘下来”或者“接回去”。只要这四个角色都清楚，边界基本不会出错。

2. 分段操作的常见类型与方案选型

分段操作看似多变，但落到实际代码里，最常见的其实就是三种模式。把这三类吃透，绝大多数场景都能套用。

2.1 按固定步长切段：每 k 个节点一组

这种模式要求把链表切成若干段，每段恰好 k 个节点。经典衍生题是“K 个一组翻转链表”，核心前提就是先按 k 个节点划分出段。实现时用双指针：一个 cur 从 pre 的下一步出发，走 k 步。如果走满 k 步说明完整段存在，pre 和 cur 分别指向段的前端入口和段尾；如果走不完说明剩余不足 k 个节点，就按剩余情况处理。

这里的选型重点是：切段时是拆成独立链还是原地处理。如果业务要求后续每段独立操作，那就要把每一段的段尾 next 置空；如果只是“标记范围然后原地做处理”，那么段尾不需要断开，只要记住 end 的位置即可。

我自己的建议是：默认先不物理断开，因为物理断开后还要重新接，多做一次无意义操作。只有目标确实需要多个独立链表时才断开。

2.2 按值分区：单次遍历完成大于/小于切分

按值分区在链表题里出镜率极高。给定一个阈值 x，把所有 val 小于 x 的节点全部挪到大于等于 x 的节点之前，并且保持原有的相对顺序。数组实现可以直接额外开两个数组，链表不行，因为节点对象只有一个 next 指针，你不能同时让一个节点属于两个集合。

主流的可靠方案是“双哑节点法”：建立 smallHead 和 largeHead 两个哑节点，各自拖着一条尾部链。遍历原链，val 小于 x 的节点接到 smallTail 后面，其余接到 largeTail 后面。遍历结束时把 smallTail 的 next 接上 largeHead.next，新链的 head 就是 smallHead.next。

这个方法的好处是每个节点只被访问一次，不产生额外空间，而且天然保持稳定性。相比之下，有人喜欢反复从原链上找到最小节点再摘下来接新链，那是最差的做法，时间复杂度和指针细节都容易失控。

2.3 按段聚合处理：段反转、段排序、段求和

除了切分和分区，还有一种场景是“先把链分成若干段，然后对段做聚合操作”。比如段内反转、段内统计总和、段内求最大值。这种处理模式下，段本身不是最终目标，段的处理结果才是。

这类问题的实现套路是：外层循环负责确定每段的边界，内层处理函数负责对段范围做聚合。关键技巧是每个段处理完后，要把 pre 更新为当前段的真实结尾，否则下一轮循环会从错误位置出发。很多人在 K 组反转题里出错，就是因为每段反转后 pre 还停在老位置。

3. 手把手实现一个“链表分段”工具

理论说再多不如直接跑一遍代码。我习惯用无第三方依赖的原生链表来演示，这样能看得懂每个 next 的走向。下面基于常见的链表结构来写。

3.1 先搭好基础结构：节点与验证函数

开始切段之前，先准备好节点定义、建链函数和打印函数。没有这三个，后面调试会非常痛苦。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build_link(arr): dummy = ListNode() tail = dummy for x in arr: tail.next = ListNode(x) tail = tail.next return dummy.next def print_link(head): res = [] cur = head while cur: res.append(str(cur.val)) cur = cur.next print(" -> ".join(res)) return res

建链函数返回链表的 head。打印函数可以把整个链变成文本，方便在分段前后做对比。特别注意，打印函数不要对链表做任何修改，否则调试时容易把原链搞坏。我见过有人在 print 函数里顺手排序，原链被改得面目全非，排查了大半天。

3.2 切段核心逻辑：记录 pre 与 next 是关键

下面实现按固定长度切段的完整函数。需求是：给定链表 head 和整数 k，把链表切成若干段，每段长度尽量接近 k。段与段之间按顺序返回，每段都是一个独立的链表头。

def split_by_k(head, k): # 第一遍：统计链表长度 n = 0 cur = head while cur: n += 1 cur = cur.next # 计算每段的基础长度和需要加长的段数 base_len = n // k extra = n % k result = [] cur = head for i in range(k): seg_head = cur seg_len = base_len + (1 if i < extra else 0) # 走 seg_len - 1 步到达段尾 for _ in range(seg_len - 1): if cur: cur = cur.next if cur: nxt = cur.next cur.next = None cur = nxt result.append(seg_head) return result

这里的处理逻辑是现实中最常用的一种：把链表尽量均匀地切成 k 段，前 extra 段比后面多一个节点。核心动作在 for 循环里：先记下 seg_head 作为当前段头，然后走 seg_len - 1 步到段尾，保存 nxt 之后把 cur.next 置空，实现物理切分。

有两个细节容易出错。第一个是 seg_len 可能为 0，意味着对应段是空段，这时候 seg_head 本来就是 None，循环里不会进去，直接 append None 即可。第二个是 n 小于 k 时，base_len 为 0，extra 等于 n，前 n 段各一个节点，后 k - n 段都是空段，这个函数也能正确输出。

3.3 分区实现：双哨兵节点减少特判

再来看按值分区。需求是：给定阈值 x，让所有 val 小于 x 的节点都在大于等于 x 的节点之前，并且保持相对顺序。

def partition_by_value(head, x): 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 = cur else: large_tail.next = cur large_tail = cur cur.next = None cur = nxt small_tail.next = large_dummy.next return small_dummy.next

这段代码看起来很短，但每一行都有讲究。第一，遍历时必须先取 nxt 再操作 cur，因为 cur.next 马上会被改写。第二，每次把 cur 接到新链尾后立刻把 cur.next 置空，这一步是为了防止 cur 把后面的整条链“顺带挂到”新链上。第三，最后只需要让 small_tail.next 指向 large_dummy.next，就完成了两条逻辑段的拼接。

如果漏掉 cur.next = None 这一步，后果是：第一个大节点接上 large_tail 时，它后面还拖着整条原链，遍历又没有及时保存后续节点，那么整个循环会直接在错误链上回溯，轻则输出错乱，重则形成循环引用。这个坑我至少见过三次，都是同样的原因。

3.4 复杂度与参数权衡

按固定步长切段的实现先统计长度再切分，时间复杂度 O(n)，额外空间 O(1)，不依赖递归也不产生辅助数组。按值分区同样是 O(n) 时间和 O(1) 空间，并且是稳定分区。

选型时需要考虑一个核心权衡：是否允许破坏原链。上面的实现都属于“原地修改”型，原链在操作后会消失。如果调用方还需要保留原始链表，就必须在操作前做一次完整复制。链表复制的代价是 O(n) 额外空间，但也能保证原数据不被污染。很多业务事故的发生不是算法写错，而是没搞清这个函数到底允不允许修改入参。

4. 实战踩坑记录：最常见的四个问题

链表分段写起来不算长，可真跑起来遇到的坑比数组操作多得多。下面几个问题都是我实际调试时遇到过、或者帮别人 debug 时见过的，每一条都值得记住。

4.1 指针丢失：断链之后失去访问入口

指针丢失是最常见也最危险的问题。典型代码是这样写的：

cur = head while cur: cur.next = new_tail.next # 覆盖了 cur.next new_tail.next = cur cur = cur.next # cur 已经指向错误位置

问题在于：当把 cur.next 指向新位置后，原来的 next 信息就没了，下一步 cur = cur.next 走的已经不再是原链的后续节点。正确做法是先保存原始下一个节点：nxt = cur.next，所有操作完成后再 cur = nxt。这个顺序不能变。我的经验是，只要看到对 cur.next 赋值，就下意识在上一行加一句 nxt = cur.next。

4.2 意外成环：尾节点没有置空

分区操作里很容易出现成环现象。比如把节点接到新链时没有把 cur.next 置空，两个集合的尾部就会互相引用，或者大集合尾节点还指向小集合里的某个节点，构成一个环。出现环之后，任何遍历函数都会死循环，且很难定位。

一种有效的自查方法是在打印函数里加一个简单的计数保护：如果打印的节点数超过预期链表长度两倍，立刻抛出异常。

def safe_print(head, max_nodes=1_000_000): res = [] cur = head cnt = 0 while cur and cnt < max_nodes: res.append(str(cur.val)) cur = cur.next cnt += 1 assert cnt < max_nodes, "检测到疑似环，遍历超过最大节点数" print(" -> ".join(res))

虽然这种做法不能根治问题，但能第一时间暴露它，调试效率至少翻倍。

4.3 边界条件：空链、单节点、k 等于 1

链表操作里，空链、单节点、k 等于 1 这三类边界条件最容易出 bug。空链的 head 为 None，切分函数应该返回全空段的列表而不是崩溃；单节点链只走一步，循环里 pre 和 cur 的更新逻辑不能越界；k 等于 1 时每段只有一个节点，分段前后的 next 修改频率最高，稍微写错一个就乱套。

我的建议是把这三类边界写进测试用例，每次改完代码先跑一遍再提交。不要依赖“感觉应该没问题”，链表这个东西，边界问题永远只能靠实际执行暴露。

4.4 调试技巧：小样例、断言、画图验证

链表分段调试有一个很好用的组合拳。第一步，把输入规模缩小到 0、1、2、5 个节点，每个长度跑一遍，观察输出是否符合预期。第二步，在每个重要节点操作前后加断言，比如检查 pre.next 是否等于预期节点、段长是否符合计算值。第三步，把链表打印成“a -> b -> c”的文本格式，操作前后各打印一次，肉眼比对差异。

有一个不太常提但很有效的小技巧：在修改 next 的时候，临时把节点值也改成一个特殊标记，跑完再还原。这样如果输出链上出现了标记节点，说明某个本该断开的旧边没断开。这个技巧帮我定位过一次非常隐蔽的成环问题，比对着代码干瞪眼高效得多。

最后分享一点个人心得

链表分段这类问题的真正难点从来不是算法思想，而是对指针细节的敬畏。我自己的习惯是：所有链表操作都默认原地修改，所有修改 next 的地方都先想一遍“如果我只有一个节点，这个操作还成立吗”。每次写完，跑一遍 0、1、2、5 个节点的测试再收工。这个习惯帮我避免了很多线上问题。如果你刚开始接触链表分段，建议先手动画几条短的链，把 pre、start、end、after 四个角色的关系弄清楚，再去看代码实现，你会发现代码突然变得好懂很多。