21. 合并两个有序链表（简单）

Blind 75 › 21. 合并两个有序链表（简单） （第 2 章）
文章工具

题目

给定两个升序排列的单链表，把它们合并成一条新的升序链表并返回。新链表由两条原链表的节点直接拼接而成（可以复用原节点，不要求新建节点）。

换句话说：每次只看两条链当前最前面的节点，把值较小的那个接到结果末尾；一条链走完后，把另一条剩余部分整段接上即可。

自造示例：list1 = [1,2,4]、list2 = [1,3,4] → [1,1,2,3,4,4]；list1 = [2,5]、list2 = [1,3,6] → [1,2,3,5,6]。

约束：两条链表的节点总数在 0 ~ 50；节点值 -100 ~ 100；两条链表均按非递减顺序排列。

思路

一句话：两条链都已有序，每个位置只要在两个“当前头节点”里取较小者接上即可。

先想最直白的：把所有节点值收集到一个数组，整体排序，再重建链表。这样一定正确，但时间 O((m+n) log(m+n))、空间 O(m+n)，白白浪费了“两条链已经各自有序”的条件。

再想“边比较边接”：既然每条链内部已经排好，那么结果链的下一个最小值，只可能是 list1 当前头节点或 list2 当前头节点中较小的那个。每次取走它、推进对应指针，就像归并排序里的合并一步。

关键观察：这个“每次取较小者”的贪心不会错过任何节点——被跳过的一方之后只会变大或相等，不可能产生更小的值，所以合并结果必然整体升序。

实现上用一个虚拟头节点 dummy 统一“结果为空”和“结果非空”两种情况，避免特判第一个节点。

解法

设 tail 始终指向结果链的最后一个节点，dummy.next 是结果链真正的头：

  1. 当两条链都非空：比较 list1.val 与 list2.val，把较小节点接到 tail.next，对应链指针后移，tail 也后移。
  2. 循环结束说明至少一条链为空，把仍非空的那条整段接到 tail.next。
  3. 返回 dummy.next。
步骤list1 当前list2 当前取谁结果链
111list1 的 1[1]
221list2 的 1[1,1]
323list1 的 2[1,1,2]
443list2 的 3[1,1,2,3]
544list1 的 4[1,1,2,3,4]
6空4整段接上[1,1,2,3,4,4]

相等时取任意一条都行；代码里写 <= 取 list1，是为了保持稳定（原 list1 在前）。

下图把上面 3 个步骤串成流程，并逐步演示：

21. 合并两个有序链表（简单） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
21. 合并两个有序链表（简单） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);                 // 栈上哨兵，避免 new 造成内存泄漏
        ListNode* tail = &dummy;

        while (list1 && list2) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        tail->next = list1 ? list1 : list2;   // 接上没走完的那条
        return dummy.next;
    }
};

Python

Python 3 示例