わたしの部屋

范围#

题型归纳#

题型： 链表分区

题目特征： 需要把小于 x 的节点放到前面，大于等于 x 的节点放到后面，并且保留每个分区内部的原始相对顺序。

解法： 准备两条链表，分别收集 < x 和 >= x 的节点，最后把两条链表拼接起来。

易错点： 节点摘下后要断开 next，追加节点后要更新尾指针，小于区为空时要直接返回大于等于区。

看到”分区且保留相对顺序”就是稳定分区的信号——这里不是排序，而是稳定分区。核心做法是维护两条链表各自的头尾指针，遍历时把节点逐一摘下接入对应区，最后拼接；最容易出错的是摘节点时忘记断开 head.next，导致旧的 next 关系污染新链表结构。

题意#

给你一个链表的头节点 head 和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前，并且保留两个分区中每个节点的初始相对位置。

示例#

示例 1：

输入： head = [1,4,3,2,5,2], x = 3

输出： [1,2,2,4,3,5]

示例 2：

输入： head = [2,1], x = 2

输出： [1,2]

提示#

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

核心思路#

这道题不是排序，而是稳定分区——>= x 的节点之间不会被重新排列，只是整体移到后面。

准备两条链表：left 收集所有 < x 的节点，right 收集所有 >= x 的节点。遍历原链表时，把每个节点先断开 next，再接到对应链表的尾部。遍历结束后把两条链表拼接即可。

4 -> 3 -> 5 不会变成 3 -> 4 -> 5，因为要求保留原始相对顺序，这是和排序最根本的区别。

核心模板#

1
public static ListNode partition(ListNode head, int x) {
2
    ListNode leftHead = null, leftTail = null;
3
    ListNode rightHead = null, rightTail = null;
4

5
    while (head != null) {
6
        ListNode next = head.next;
7
        head.next = null;
8

9
        if (head.val < x) {
10
            if (leftHead == null) {
11
                leftHead = head;
12
                leftTail = head;
13
            } else {
14
                leftTail.next = head;
15
                leftTail = head;
16
            }
17
        } else {
18
            if (rightHead == null) {
19
                rightHead = head;
20
                rightTail = head;
21
            } else {
22
                rightTail.next = head;
23
                rightTail = head;
24
            }
25
        }
26

27
        head = next;
28
    }
29

30
    if (leftHead == null) {
31
        return rightHead;
32
    }
33
    leftTail.next = rightHead;
34
    return leftHead;
35
}

变量角色#

leftHead 和 rightHead 分别记住两条链表的头节点；leftTail 和 rightTail 始终指向各自链表的尾节点，每接入一个新节点就跟着往后移动一位；next 临时保存原链表的下一个节点，在断开 head.next 之前必须先保存，否则后续节点会丢失。

过程拆解#

1. 保存并断开：每轮先把 head.next 存入 next，再把 head.next 置为 null，把当前节点单独摘出来。
2. 按值分流：head.val < x 接入 left，否则接入 right；第一次接入时同时设置头尾指针，之后只更新尾指针。
3. 推进遍历：head = next 走到下一个节点。
4. 收尾拼接：leftHead == null 时直接返回 rightHead；否则把 leftTail.next 指向 rightHead，返回 leftHead。

易错点#

• 每次追加节点后必须更新尾指针（leftTail = head / rightTail = head），否则尾指针停在第一个节点，后续每次都覆盖同一个 next，前面的节点全部丢失。
• leftHead == null 时直接返回 rightHead，不需要拼接。反过来 rightHead == null 时不需要特判，因为 leftTail.next = null 本身就是合法的。

摘节点时忘记断开 head.next

错误写法：只保存 next，没有把 head.next 置为 null：

1
ListNode next = head.next;
2
// 漏写 head.next = null;
3

4
if (head.val < x) {
5
    leftTail.next = head;
6
    leftTail = head;
7
}
8
head = next;

为什么错：head 带着原来的 next 被接入新链表，它的 next 仍然指向原链表中的后续节点，新链表的结构会被旧连接污染，最终形成环或者串入不该出现的节点。

正确写法：

1
ListNode next = head.next;
2
head.next = null; // 先断干净，再接入新链表

口诀

保存 next，断开当前，按值接尾，最后 left 拼 right。