链表分割算法详解：双指针实现与应用场景

发布时间：2026/10/28 23:49:30

1. 链表分割问题概述

链表分割是数据结构中的经典问题，题目要求给定一个链表和一个特定值x，将链表分隔成两部分，使得所有小于x的节点都出现在大于或等于x的节点之前。这个操作需要保持原始链表中节点的相对顺序。

在实际开发中，这类操作常见于数据过滤、条件分组等场景。比如在电商系统中，我们可能需要将用户订单按金额阈值分组处理；在日志分析时，按错误级别分离日志条目。理解链表分割的算法原理，对处理这类线性数据分组问题很有帮助。

2. 问题分析与解法思路

2.1 需求拆解

题目要求的关键点有三个：

分区条件：节点值小于x的在前，大于等于x的在后
稳定性：保持原有节点的相对顺序
就地操作：最好在不创建新链表的情况下完成

2.2 常见解法对比

2.2.1 双指针法

创建两个虚拟头节点，分别连接小于x和大于等于x的节点，最后合并。这种方法时间复杂度O(n)，空间复杂度O(1)，是最优解。

2.2.2 节点交换法

类似快速排序的partition操作，通过交换节点实现分割。但会破坏稳定性，不满足题目要求。

2.2.3 数组辅助法

将链表转为数组处理后再重建链表。虽然直观但空间复杂度高(O(n))，且失去了链表处理的优势。

提示：在实际面试中，面试官通常会期望采用双指针法，因为它兼顾了时间效率和空间效率。

3. 双指针法详细实现

3.1 算法步骤拆解

初始化两个虚拟头节点：before_head和after_head
创建两个指针before和after分别指向这两个虚拟头节点
遍历原始链表：
- 当前节点值 < x：连接到before链表
- 当前节点值 >= x：连接到after链表
合并两个链表：before末尾接after_head.next
返回before_head.next

3.2 C++实现示例

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode before_head(0), after_head(0); ListNode *before = &before_head, *after = &after_head; while(head) { if(head->val < x) { before->next = head; before = before->next; } else { after->next = head; after = after->next; } head = head->next; } after->next = NULL; // 防止循环链表 before->next = after_head.next; return before_head.next; } };

3.3 Python实现示例

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def partition(self, head: ListNode, x: int) -> ListNode: before = before_head = ListNode(0) after = after_head = ListNode(0) while head: if head.val < x: before.next = head before = before.next else: after.next = head after = after.next head = head.next after.next = None # 避免循环引用 before.next = after_head.next return before_head.next