LeetCode 剑指 Offer 25. 合并两个排序的链表

2023-03-28 HGNULB 约 5 分钟

文章信息 14 个分类 2 个标签

分类

LeetCode CodeTop 简单已解决已掌握 5-10 字节跳动美团快手猿辅导百度京东剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 25. 合并两个排序的链表

题意分析

输入是两条各自已经从小到大排好序的单链表，要把它们拼成一条同样有序的链表并返回新的头节点。题目对新链表的构成方式通常允许直接复用原有节点，也就是只改指针不新建节点。

「各自已经有序」是这题唯一的、也是全部的杠杆。它意味着两条链表当前最前面的两个节点里，一定有一个是全部剩余节点中最小的那个——除此之外的任何节点，都被自己链表里排在它前面的节点压着。这个性质让每一步的决策变成一次二选一的比较，不需要任何回头看。

边界要考虑得细一点：两条链表都可能为空，也可能只有一条为空；两条链表长度可以差很多，短的先走完之后长的会整段剩下；两边可能存在相等的值，此时选哪一条都不影响有序性，但如果在意稳定性（相等时优先取第一条），比较符号的取舍就有讲究。另外返回的头节点未必属于任何一条原链表的原始头，所以不能简单地返回其中之一。

解法：双指针归并链表

核心思路

问题关键： 两条链表各自有序，所以全部未处理节点中的最小值，一定是两个当前头节点中的较小者。无需重新排序，也无需复制节点。

用 l1、l2 指向两条链表尚未合并的首节点，每次把较小节点接到结果尾部并推进对应指针。哑节点 dummy 统一处理结果为空和追加第一个节点的情况。

不变量： 每轮开始时，dummy.next 到 tail 已经包含所有被处理节点且保持有序；l1、l2 分别指向两条剩余链表的最小节点。选择两者中较小者后，结果仍有序，且没有遗漏节点。

正确性： 当前较小节点不大于任一剩余节点，把它放在结果的下一个位置是唯一安全的贪心选择。循环结束时，未空链表整体有序，且其首值不小于 tail，可一次性接到尾部。

解题步骤

创建哑节点，令 tail 指向它。

当两条链表都非空时，比较当前节点，把较小者接到 tail.next，并推进对应指针。

将 tail 移到刚接入的节点。

一条链表为空后，把另一条的剩余部分整体接上。

返回 dummy.next。

口述示例： 1 -> 2 -> 4 与 1 -> 3 -> 4 依次选择 1、1、2、3、4；第一条耗尽后直接接上第二条剩余的 4，得到 1 -> 1 -> 2 -> 3 -> 4 -> 4。

边界： 任一链表为空时循环不会执行，收尾会直接返回另一条；相等时用 <= 优先选择第一条，可保持稳定性。

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

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

        tail.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }

    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }
    return dummy.Next
}

复杂度分析

时间复杂度：$O(m+n)$，每个节点至多被处理一次。

空间复杂度：$O(1)$，只使用哑节点和若干指针；原有节点被复用。

关键点总结

有序链表的当前头节点就是各自剩余部分的最小值。

哑节点消除了结果头节点的特殊分支。

每轮只推进被接入的链表，随后再推进 tail。

一条链表耗尽后，另一条剩余部分可整体拼接。

易错点总结

两个指针每轮同时前进：未被选择的节点会丢失。

忘记拼接剩余链表：较长链表的尾部会丢失。

返回 dummy 而不是 dummy.next：结果会多出虚拟头节点。

若业务不允许修改输入链表，不能复用节点；需要新建结果节点并承担 $O(m+n)$ 空间。

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	同一模型的另一份题面，适合对照迭代与递归两种写法
23. 合并 K 个升序链表	困难	由两条推广到 K 条，需要优先队列或分治两两归并
88. 合并两个有序数组	简单	换成数组且要求原地合并，得从后往前填以避免覆盖
148. 排序链表	中等	把本题当作归并排序的合并步骤，再补上快慢指针拆分
86. 分隔链表	中等	归并的逆操作：按阈值拆成两条再首尾相接，同样靠哑节点
LCR 078. 合并 K 个升序链表	困难	与 23 同源，可用来比较堆解法与分治解法的常数与代码量