链表的分解：双 Dummy 节点分离再拼接

1089 字

5 分钟

链表的分解：双 Dummy 节点分离再拼接

2026-08-10

算法

链表

/

双指针

/

分解

/

C

/

C++

/

JavaScript

题目描述#

给定一个链表和一个特定值 x，将链表重新排列，使得所有小于 x 的节点出现在大于或等于 x 的节点之前。同时保留两部分内部节点的原始相对顺序。

1
输入：head = 1→4→3→2→5→2, x = 3
2
输出：1→2→2→4→3→5
3
解释：小于 3 的：1, 2, 2（保持原序）
4
      大于等于 3 的：4, 3, 5（保持原序）

解题思路#

核心思想：双 Dummy 分离#

直观想法是创建两个新链表——一个装”小值”，一个装”大值”——遍历原链表时把每个节点归到对应的链表。遍历完毕后，把小值链表的尾部接到大值链表的头部即可。

但直接操作”新链表的头指针”会遇到”第一个节点是谁”的边界问题。所以我们用两个 dummy 虚拟头节点 来分别管理两条链。

算法步骤#

创建 smallDummy 和 largeDummy 两个虚拟头节点
用 small 和 large 尾指针分别维护两个链表
遍历原链表，根据节点值与 x 的比较将节点归入对应链表
遍历结束后，将 large 链表接到 small 链表尾部
关键：将 large.next 置为 null，否则可能形成环
返回 smallDummy.next

为什么必须置 large.next = null？ 大值链表的最后一个节点可能原本指向一个大值节点，如果不断开，拼接后链表末尾可能指向旧节点形成环。

代码实现#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* partition(ListNode* head, int x) {
10
    // 创建两个 dummy 虚拟头节点
11
    ListNode smallDummy, largeDummy;
12
    smallDummy.next = NULL;
13
    largeDummy.next = NULL;
14
    ListNode *small = &smallDummy;
15
    ListNode *large = &largeDummy;
16

17
    // 遍历原链表，分离节点
18
    ListNode *curr = head;
19
    while (curr) {
20
        if (curr->val < x) {
21
            small->next = curr;
22
            small = small->next;
23
        } else {
24
            large->next = curr;
25
            large = large->next;
26
        }
27
        curr = curr->next;
28
    }
29

30
    // 拼接两个链表
31
    small->next = largeDummy.next;
32
    // 断开大值链表末尾，防止环
33
    large->next = NULL;
34

35
    return smallDummy.next;
36
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};
8

9
class Solution {
10
public:
11
    ListNode* partition(ListNode* head, int x) {
12
        // 创建两个 dummy 虚拟头节点
13
        ListNode smallDummy(0), largeDummy(0);
14
        ListNode *small = &smallDummy;
15
        ListNode *large = &largeDummy;
16

17
        // 遍历原链表，分离节点
18
        ListNode *curr = head;
19
        while (curr) {
20
            if (curr->val < x) {
21
                small->next = curr;
22
                small = small->next;
23
            } else {
24
                large->next = curr;
25
                large = large->next;
26
            }
27
            curr = curr->next;
28
        }
29

30
        // 拼接两个链表
31
        small->next = largeDummy.next;
32
        // 断开大值链表末尾，防止环
33
        large->next = nullptr;
34

35
        return smallDummy.next;
36
    }
37
};

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
function partition(head, x) {
9
    // 创建两个 dummy 虚拟头节点
10
    const smallDummy = new ListNode(0);
11
    const largeDummy = new ListNode(0);
12
    let small = smallDummy;
13
    let large = largeDummy;
14

15
    // 遍历原链表，分离节点
16
    let curr = head;
17
    while (curr) {
18
        if (curr.val < x) {
19
            small.next = curr;
20
            small = small.next;
21
        } else {
22
            large.next = curr;
23
            large = large.next;
24
        }
25
        curr = curr.next;
26
    }
27

28
    // 拼接两个链表
29
    small.next = largeDummy.next;
30
    // 断开大值链表末尾，防止环
31
    large.next = null;
32

33
    return smallDummy.next;
34
}

图解过程#

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

3
初始状态：
4
smallDummy → ?
5
largeDummy → ?
6

7
Step 1: curr=1, 1<3 → 归入 small
8
smallDummy → 1
9
largeDummy → ?
10

11
Step 2: curr=4, 4≥3 → 归入 large
12
smallDummy → 1
13
largeDummy → 4
14

15
Step 3: curr=3, 3≥3 → 归入 large
16
smallDummy → 1
17
largeDummy → 4→3
18

19
Step 4: curr=2, 2<3 → 归入 small
20
smallDummy → 1→2
21
largeDummy → 4→3
22

23
Step 5: curr=5, 5≥3 → 归入 large
24
smallDummy → 1→2
25
largeDummy → 4→3→5
26

27
Step 6: curr=2, 2<3 → 归入 small
28
smallDummy → 1→2→2
29
largeDummy → 4→3→5
30

31
拼接并断开 large 末尾：
32
结果：1→2→2→4→3→5