86. 分隔链表

题目描述

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得：

所有 小于 x 的节点都出现在
所有 大于等于 x 的节点之前

你应当 保留两个分区中每个节点的初始相对位置。

示例 1

text

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

示例 2

text

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

约束

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

核心思路

这题的重点不是排序，而是：

把链表拆成两部分
再按顺序拼回去
并且 保持原有相对顺序不变

也就是说：

所有 < x 的节点，内部顺序不能乱
所有 >= x 的节点，内部顺序也不能乱

所以这题本质上是在做一个：

稳定分组

这题至少有两种常见做法：

解法一：两条链表分别收集后再拼接（推荐）
解法二：数组暂存节点后重连

先理解：为什么不能直接交换值或随便换位置？

题目要求的是：

小于 x 的在前
大于等于 x 的在后
相对顺序保持不变

比如：

text

head = [1,4,3,2,5,2], x = 3

小于 3 的节点按原顺序是：

text

1, 2, 2

大于等于 3 的节点按原顺序是：

text

4, 3, 5

所以答案必须是：

text

1, 2, 2, 4, 3, 5

不能把它排成：

text

1, 2, 2, 3, 4, 5

因为那样已经改变了 4, 3, 5 这部分的相对顺序。

所以这题不能理解成排序题，而要理解成“稳定地分成两组”。

解法一：两条链表分别收集后再拼接

这是这题最经典、最推荐掌握的做法。

思路拆解

我们准备两条链表：

small：存所有 < x 的节点
large：存所有 >= x 的节点

然后遍历原链表：

如果当前节点值 < x，接到 small 链表后面
否则接到 large 链表后面

最后再把：

text

small -> large

拼起来即可。

因为我们是按原链表遍历顺序依次追加到各自链表尾部，所以每一组内部顺序天然不变。

为什么要用虚拟头节点？

如果直接维护链表头，第一次插入时会很麻烦。

所以通常会准备：

smallDummy
largeDummy

这样不管这一组有没有元素，后面拼接都更统一。

一步一步写出算法

第一步：定义两条链表的虚拟头节点

const smallDummy = new ListNode(0)
const largeDummy = new ListNode(0)

再定义两个尾指针：

let smallTail = smallDummy
let largeTail = largeDummy

第二步：遍历原链表

let cur = head
while (cur !== null) {
    ...
}

遍历过程中，我们要先保存下一节点：

const next = cur.next

因为后面可能会改 cur.next。

第三步：按值分到两条链表

如果 cur.val < x：

smallTail.next = cur
smallTail = smallTail.next

否则：

largeTail.next = cur
largeTail = largeTail.next

第四步：断开当前节点原来的后继

这一点很重要。

cur.next = null

为什么要断开？

因为当前节点原来还连着原链表后面的节点，如果不及时断开，最后拼接时可能把旧链路带进来，形成错误结构。

第五步：继续遍历

cur = next

第六步：最后把两条链表拼起来

smallTail.next = largeDummy.next

答案就是：

return smallDummy.next

代码实现（TypeScript）

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function partition(head: ListNode | null, x: number): ListNode | null {
    const smallDummy = new ListNode(0)
    const largeDummy = new ListNode(0)
    let smallTail = smallDummy
    let largeTail = largeDummy

    let cur = head
    while (cur !== null) {
        const next = cur.next
        cur.next = null

        if (cur.val < x) {
            smallTail.next = cur
            smallTail = smallTail.next
        } else {
            largeTail.next = cur
            largeTail = largeTail.next
        }

        cur = next
    }

    smallTail.next = largeDummy.next
    return smallDummy.next
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

这里只用了几个指针，没有额外按节点数增长的空间。

这一解法的优缺点

优点：

思路最清楚
稳定分组非常自然
是这题标准解法

缺点：

需要注意断链和最后拼接

解法二：数组暂存节点后重连

这个做法更直观，但不是空间最优。

思路拆解

我们也可以先遍历链表，把节点分成两个数组：

smallNodes
largeNodes

遍历完成后：

先把 smallNodes 里的节点按顺序连起来
再把 largeNodes 里的节点按顺序连起来

因为数组是按遍历顺序加入节点，所以相对顺序仍然保持不变。

一步一步写出算法

第一步：定义两个数组

const smallNodes: ListNode[] = []
const largeNodes: ListNode[] = []

第二步：遍历链表并分类

let cur = head
while (cur !== null) {
    const next = cur.next
    cur.next = null

    if (cur.val < x) {
        smallNodes.push(cur)
    } else {
        largeNodes.push(cur)
    }

    cur = next
}

第三步：合并顺序

const nodes = [...smallNodes, ...largeNodes]

第四步：重新连接

for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].next = nodes[i + 1]
}

如果数组为空，返回 null；否则返回第一个节点。

代码实现（TypeScript）

class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}

function partition(head: ListNode | null, x: number): ListNode | null {
    const smallNodes: ListNode[] = []
    const largeNodes: ListNode[] = []

    let cur = head
    while (cur !== null) {
        const next = cur.next
        cur.next = null

        if (cur.val < x) {
            smallNodes.push(cur)
        } else {
            largeNodes.push(cur)
        }

        cur = next
    }

    const nodes = [...smallNodes, ...largeNodes]
    if (nodes.length === 0) {
        return null
    }

    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1]
    }

    return nodes[0]
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

因为用了两个数组来保存节点。

这一解法的优缺点

优点：

很直观
很适合第一次理解“稳定分组”

缺点：

用了额外数组
不是题目更推荐的链表原地思路

两种解法对比

解法	时间复杂度	空间复杂度	特点
两条链表拼接	`O(n)`	`O(1)`	标准解法，最推荐
数组暂存后重连	`O(n)`	`O(n)`	更直观，但不够优

如果你是第一次做这题，可以先理解第二种；但面试里更建议写第一种。

手动模拟一遍标准解法

以：

text

head = [1,4,3,2,5,2], x = 3

为例。

遍历到 `1`

因为：

text

1 < 3

所以放进 small：

text

small: 1
large: 空

遍历到 `4`

因为：

text

4 >= 3

所以放进 large：

text

small: 1
large: 4

遍历到 `3`

因为：

text

3 >= 3

继续放进 large：

text

small: 1
large: 4 -> 3

遍历到 `2`

因为：

text

2 < 3

放进 small：

text

small: 1 -> 2
large: 4 -> 3

遍历到 `5`

放进 large：

text

small: 1 -> 2
large: 4 -> 3 -> 5

遍历到最后一个 `2`

放进 small：

text

small: 1 -> 2 -> 2
large: 4 -> 3 -> 5

最后拼接

text

1 -> 2 -> 2 -> 4 -> 3 -> 5

这就是答案。

面试时最容易错的点

1. 这题不是排序题

它不要求：

所有小的按数值排序
所有大的按数值排序

它要求的是：

按照原有顺序稳定分组

2. 一定要保留相对顺序

比如 >= x 那一组里：

text

4, 3, 5

顺序不能变成：

text

3, 4, 5

3. 遍历时最好先保存 `next`

因为你会修改：

cur.next = null

如果不先保存下一节点，后面链表就断掉了。

4. 大链表尾巴别忘了断开

如果不及时断开旧的 next，拼接后可能残留原来的指向关系，导致链表结构错误。

5. 最后要把两条链表接起来

很多人分完组之后，忘了最后这句：

smallTail.next = largeDummy.next

一句话总结

这题的本质是：

把链表稳定地分成 < x 和 >= x 两组，再按顺序拼回去。

想写标准解：用 两条链表分别收集后拼接
想先直观理解：用 数组暂存节点后重连

86. 分隔链表

题目描述

示例 1

示例 2

约束

核心思路

先理解：为什么不能直接交换值或随便换位置？

解法一：两条链表分别收集后再拼接

思路拆解

为什么要用虚拟头节点？

一步一步写出算法

第一步：定义两条链表的虚拟头节点

第二步：遍历原链表

第三步：按值分到两条链表

第四步：断开当前节点原来的后继

第五步：继续遍历

第六步：最后把两条链表拼起来

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：数组暂存节点后重连

思路拆解

一步一步写出算法

第一步：定义两个数组

第二步：遍历链表并分类

第三步：合并顺序

第四步：重新连接

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍标准解法

遍历到 1

遍历到 4

遍历到 3

遍历到 2

遍历到 5

遍历到最后一个 2

最后拼接

面试时最容易错的点

1. 这题不是排序题

2. 一定要保留相对顺序

3. 遍历时最好先保存 next

4. 大链表尾巴别忘了断开

5. 最后要把两条链表接起来

一句话总结

推荐你最后记住的标准写法

遍历到 `1`

遍历到 `4`

遍历到 `3`

遍历到 `2`

遍历到 `5`

遍历到最后一个 `2`

3. 遍历时最好先保存 `next`