分隔链表
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1
示例 2
模拟答题者思考
1. 我先写暴力：把链表所有值拷进数组，按是否 <x 分成两段再重建链表——正确且能保留相对顺序，但多用了 O(n) 额外数组，也没利用「只改指针」这一链表优势。
2. 重复在哪里？题目不要求排序，只要求「小于 x 的在前、其余在后，且各段内相对顺序不变」——等价于稳定地把节点分成两桶，再头尾相接。
3. 双桶尾插：维护 small 与 large 两条链，各配哨兵 + 尾指针；扫原链时，节点直接挂到对应桶尾部（尾插保证桶内顺序与原链一致）。
4. 扫完后把 large 头接到 small 尾后；务必令 large_tail.next = None，否则原链末尾可能仍指向旧后继，形成环。
5. 每个节点只访问一次，时间 O(n)；仅常数个指针，空间 O(1)（不计返回链表本身）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
small_dummy / large_dummy | ListNode* | 定义：两条结果链表的哨兵头，不存有效值 维护：分别锚定「<x 段」与「≥x 段」的起始位置 更新：创建后不再移动，最终用 small_dummy.next 作为答案头 |
small_tail / large_tail | ListNode* | 定义：两条分区链表的尾指针 维护：始终指向各自已拼接部分的最后一个节点 更新：每接入一个节点后 tail = tail.next |
curr | ListNode* | 定义：原链表中当前待分类的节点 维护：从 head 沿 next 扫完整条链更新：每轮先按 curr.val 挂到对应尾后，再 curr = curr.next |
落码步骤
1. 创建 small_dummy、large_dummy，尾指针 small_tail、large_tail 初始指向各自哨兵
2. curr = head，当 curr 非空：若 curr.val < x 挂到 small 桶尾，否则挂到 large 桶尾；curr = curr.next
3. large_tail.next = None（截断 large 段，防环）
4. small_tail.next = large_dummy.next，返回 small_dummy.next
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
small_dummy = ListNode(0)
large_dummy = ListNode(0)
small_tail = small_dummy
large_tail = large_dummy
curr = head
while curr:
if curr.val < x:
small_tail.next = curr
small_tail = small_tail.next
else:
large_tail.next = curr
large_tail = large_tail.next
curr = curr.next
large_tail.next = None # 截断，避免与原链尾部成环
small_tail.next = large_dummy.next
return small_dummy.nextclass Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode smallDummy(0), largeDummy(0);
ListNode* smallTail = &smallDummy;
ListNode* largeTail = &largeDummy;
ListNode* curr = head;
while (curr) {
if (curr->val < x) {
smallTail->next = curr;
smallTail = smallTail->next;
} else {
largeTail->next = curr;
largeTail = largeTail->next;
}
curr = curr->next;
}
largeTail->next = nullptr; // 截断，避免成环
smallTail->next = largeDummy.next;
return smallDummy.next;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
忘记 large_tail.next = nullptr：原链表最后一个节点的 next 可能仍指向后续节点，拼接后会形成环或多余节点。
比较条件写错：题目是「严格小于 x」进前段，val == x 应进后段（≥x）。
用头插法建桶会破坏「相对顺序」——必须用尾插，与遍历顺序一致。
必测边界 Case
head = null, x = 1 → null
head = [1,2], x = 5 → [1,2]；head = [3,4], x = 1 → [3,4]（large 段可能为空，接尾时仍安全）
head = [2,1], x = 2 → [1,2]（2 进后段，1 进前段）