合并两个有序链表：双指针与 Dummy 节点

1010 字

5 分钟

合并两个有序链表：双指针与 Dummy 节点

2026-08-10

算法

链表

/

双指针

/

合并

/

C

/

C++

/

JavaScript

题目描述#

将两个升序链表 list1 和 list2 合并为一个新的升序链表，并返回合并后的链表头节点。新链表由两个输入链表的所有节点拼接而成。

1
输入：list1 = 1→2→4, list2 = 1→3→4
2
输出：1→1→2→3→4→4

解题思路#

核心思想：双指针逐个比较#

想象你有两叠按从小到大排好的扑克牌，你要把它们合并成一叠。每次你只需要看两叠牌最上面那张，把较小的拿走放到结果中。

对于链表，这个”比较 → 取较小者 → 指针后移”的过程可以完美地用双指针实现。

Dummy 节点的作用#

合并链表的第一个节点是谁？是 list1 的头还是 list2 的头？这个判断会让代码变得啰嗦。引入一个虚拟头节点（dummy），所有节点统一追加在 dummy 之后，最后返回 dummy.next 即可。

算法步骤#

创建 dummy 节点和尾指针 tail
同时遍历两个链表，比较当前节点值
将较小节点接在 tail 后面，对应指针后移
当任一链表遍历完毕，将剩余链表直接接在尾部
返回 dummy.next

代码实现#

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* mergeTwoLists(ListNode* list1, ListNode* list2) {
10
    // 创建 dummy 虚拟头节点
11
    ListNode dummy;
12
    dummy.next = NULL;
13
    ListNode* tail = &dummy;
14

15
    // 双指针遍历两个链表
16
    while (list1 && list2) {
17
        if (list1->val <= list2->val) {
18
            tail->next = list1;
19
            list1 = list1->next;
20
        } else {
21
            tail->next = list2;
22
            list2 = list2->next;
23
        }
24
        tail = tail->next;
25
    }
26

27
    // 将剩余链表接在尾部
28
    tail->next = list1 ? list1 : list2;
29

30
    return dummy.next;
31
}

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* mergeTwoLists(ListNode* list1, ListNode* list2) {
12
        // 创建 dummy 虚拟头节点
13
        ListNode dummy(0);
14
        ListNode* tail = &dummy;
15

16
        // 双指针遍历两个链表
17
        while (list1 && list2) {
18
            if (list1->val <= list2->val) {
19
                tail->next = list1;
20
                list1 = list1->next;
21
            } else {
22
                tail->next = list2;
23
                list2 = list2->next;
24
            }
25
            tail = tail->next;
26
        }
27

28
        // 将剩余链表接在尾部
29
        tail->next = list1 ? list1 : list2;
30

31
        return dummy.next;
32
    }
33
};

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 mergeTwoLists(list1, list2) {
9
    // 创建 dummy 虚拟头节点
10
    const dummy = new ListNode(0);
11
    let tail = dummy;
12

13
    // 双指针遍历两个链表
14
    while (list1 && list2) {
15
        if (list1.val <= list2.val) {
16
            tail.next = list1;
17
            list1 = list1.next;
18
        } else {
19
            tail.next = list2;
20
            list2 = list2.next;
21
        }
22
        tail = tail.next;
23
    }
24

25
    // 将剩余链表接在尾部
26
    tail.next = list1 ? list1 : list2;
27

28
    return dummy.next;
29
}

图解过程#

1
初始状态：
2
list1:  1 → 2 → 4
3
list2:  1 → 3 → 4
4
dummy: [ ] → ?
5

6
Step 1: 比较 1 和 1 → 取 list1 的 1
7
dummy → 1(list1)  tail=1
8

9
Step 2: 比较 2 和 1 → 取 list2 的 1
10
dummy → 1 → 1(list2)  tail=1(list2)
11

12
Step 3: 比较 2 和 3 → 取 list1 的 2
13
dummy → 1 → 1 → 2(list1)  tail=2
14

15
Step 4: 比较 4 和 3 → 取 list2 的 3
16
dummy → 1 → 1 → 2 → 3(list2)  tail=3
17

18
Step 5: 比较 4 和 4 → 取 list1 的 4
19
dummy → 1 → 1 → 2 → 3 → 4(list1)  tail=4
20

21
Step 6: list1 为空，接上 list2 剩余部分
22
dummy → 1 → 1 → 2 → 3 → 4 → 4(list2)
23

24
结果：1→1→2→3→4→4