21. 合并两个有序链表#

生活中的合并#

想象你正在整理两叠按日期排好序的收据。最自然的方式就是：拿起两叠收据，每次比较最上面的日期，选择日期较早的那张放入新的一叠中。这个简单的日常操作，恰恰就是我们今天要讨论的有序链表合并问题的真实写照。

问题描述#

题目目标#

LeetCode第21题”合并两个有序链表”要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1#

输入： 1 → 2 → 4, 1 → 3 → 4 输出： 1 → 1 → 2 → 3 → 4 → 4 链表示意：

list1: 1 -> 2 -> 4 -> null
list2: 1 -> 3 -> 4 -> null
结果:  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

text

说明： 每次取两个链表当前较小的节点，合并后的结果仍然保持升序。

示例 2#

输入： 空链表, 0 输出： 0 链表示意：

list1: null
list2: 0 -> null
结果:  0 -> null

text

说明： 其中一个链表为空时，合并结果就是另一个链表本身。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

暴力解法：转换为数组排序#

最直观的想法可能是：把两个链表的值都放到一个数组里，排序后再创建新链表。这种方法虽然不够优雅，但对于理解问题很有帮助。

暴力解法实现#

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // values：收集两个链表中的所有值，后续统一排序
    List<Integer> values = new ArrayList<>();

    // 扫描第一个链表，把节点值加入数组
    while (list1 != null) {
        values.add(list1.val);
        list1 = list1.next;
    }

    // 扫描第二个链表，把节点值加入同一个数组
    while (list2 != null) {
        values.add(list2.val);
        list2 = list2.next;
    }

    // 对所有值排序，保证后续构建出的链表为升序
    Collections.sort(values);

    // dummy：哨兵节点，简化头节点构建逻辑
    ListNode dummy = new ListNode(0);
    // current：始终指向结果链表末尾，便于尾插
    ListNode current = dummy;

    // 按排序结果逐个创建新节点并挂到结果链表尾部
    for (int value : values) {
        current.next = new ListNode(value);
        current = current.next;
    }

    // 返回真实头节点（跳过哨兵）
    return dummy.next;
}

java

优化解法：双指针遍历#

既然输入的链表已经排好序，我们完全可以模拟整理收据的过程：同时遍历两个链表，每次选择较小的节点连接到结果链表中。这就像拉链一样，将两个有序序列合并成一个。

代码实现与详解#

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // dummy：哨兵节点，统一处理头节点拼接逻辑
    ListNode dummy = new ListNode(0);
    // current：结果链表的当前尾节点
    ListNode current = dummy;

    // 只要两个链表都还有节点，就持续比较“当前最小值”
    while (list1 != null && list2 != null) {
        // list1 当前值更小（或相等）时，优先接 list1，保证稳定且有序
        if (list1.val <= list2.val) {
            current.next = list1;
            // list1 向后移动到下一个候选节点
            list1 = list1.next;
        } else {
            // 否则接入 list2 当前节点
            current.next = list2;
            // list2 向后移动
            list2 = list2.next;
        }
        // 结果链表尾指针前进
        current = current.next;
    }

    // 循环结束后，最多只有一个链表还有剩余，直接整体接到尾部即可
    if (list1 != null) {
        current.next = list1;
    }
    if (list2 != null) {
        current.next = list2;
    }

    // 返回合并后链表头（跳过哨兵）
    return dummy.next;
}

java

图解过程#

1) 初始状态：
list1: 1 → 2 → 4
list2: 1 → 3 → 4
result: dummy →

2) 第一次比较后：
list1: 2 → 4
list2: 1 → 3 → 4
result: dummy → 1 →

3) 第二次比较后：
list1: 2 → 4
list2: 3 → 4
result: dummy → 1 → 1 →

4) 最终结果：
result: dummy → 1 → 1 → 2 → 3 → 4 → 4

plaintext

复杂度比较#

暴力解法：

时间复杂度：O(nlogn)，主要来自排序过程
空间复杂度：O(n)，需要额外数组存储所有节点
缺点：没有利用链表已排序的特性

双指针解法：

时间复杂度：O(n)，只需要遍历一次
空间复杂度：O(1)，只需要几个指针
优点：充分利用了输入链表已排序的特性

技巧与思考#

哨兵节点的妙用
- 使用哨兵节点可以统一边界情况处理
- 避免了对头节点的特殊处理
就地合并的思想
- 不需要创建新节点
- 通过改变指针指向来实现合并
处理剩余节点
- 直接连接剩余链表
- 避免了继续遍历剩余节点

实际应用延伸#

合并有序链表的思想在实际开发中很常见：

数据库中的有序结果集合并
文件系统中有序文件的合并
日志系统中按时间戳排序的日志合并

小结#

合并有序链表看似简单，实则蕴含着重要的算法思想：

如何高效处理有序数据
指针操作的技巧
如何简化边界条件处理

记住：当遇到类似的合并问题时，先考虑数据是否有序，如果有序，往往可以设计出更优雅高效的解法。