算法 - 合并两个有序链表

Posted on

1. 题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1
2
3
4
5
输入: 1 -> 2 -> 4 , 1 -> 3 -> 4
输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4

输入: l1 = [], l2 = []
输出: []

节点定义：

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

2. 解题思路

经典的**归并（merge）**操作，也是归并排序的核心子步骤。

引入一个哑节点 dummy 作为结果链表的哨兵头，避免讨论「第一个节点是谁」的边界。再用 curr 指向结果链表尾部：

  1. 同时遍历 l1、l2，比较当前值，把较小的接到 curr.next，对应链表指针前移。
  2. curr 也前移一位。
  3. 有一方走完，把另一方剩余部分整段接上（它本身已有序）。
  4. 返回 dummy.next。
  • 时间复杂度：O(m + n)，每个节点处理一次。
  • 空间复杂度：O(1)，只重排指针，不新建节点。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function mergeTwoLists(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const dummy = new ListNode(-1);
    let curr = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    // 接上剩余部分（最多一条链表还有货）
    curr.next = l1 !== null ? l1 : l2;

    return dummy.next;
}

// 递归写法（更短，栈空间 O(m+n)）
function mergeTwoListsRecursive(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    if (l1 === null) return l2;
    if (l2 === null) return l1;

    if (l1.val <= l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}

4. 面试延伸

  • 合并 K 个有序链表（LeetCode 23） 是本题升级，可用「最小堆」或「分治两两合并」，复杂度 O(N log k)。
  • dummy 哑节点是链表题的通用技巧，几乎能消除所有头节点特判，务必形成肌肉记忆。
  • 稳定性：比较时用 <= 保证相等时优先取 l1，这正是归并排序「稳定」的来源。

难度：简单 | LeetCode 21 题 | 归并思想入门