CodeBrick 博客

Appearance

合并两个有序链表：直白拼接即满分 ​

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。合并两个有序链表是「链表」这一考点里最基础的归并操作，也是理解「双指针谁小谁前进」这个模式的入门题。它是经典训练题，不是真题，也不押题。

题目 ​

给定两个按值升序排列的单链表 l1、l2，将它们合并为一个新的升序链表并返回。合并后的链表应当由原两条链表的所有结点拼接而成，不新建结点。链表结点定义如下：

c
typedef struct node {
    int val;
    struct node *next;
} NODE;

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把拼接的细节写准上。

直观解法：双指针归并，谁小接谁 ​

两条链表各自升序，合并成一条升序链表的办法很直接：两个指针分别指向 l1、l2 的当前结点，每一步比较两者的值，把较小的那个接到结果链的末尾、并让那个指针前进一步；一旦有一条链先走完，把另一条剩下的部分整段接上去。

为了不必对「结果链是否为空」做特殊判断，用一个虚拟头结点 dummy 简化拼接逻辑：

c
NODE *mergeTwoLists(NODE *l1, NODE *l2) {
    NODE dummy;                        // 虚拟头结点，dummy.next 即结果链的真正头
    NODE *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;
}

拿 l1 = 1 → 3 → 5、l2 = 2 → 4 → 6 走一遍：1<2 接 1，2<3 接 2，3<4 接 3，4<5 接 4，5<6 接 5，l1 走完，把 l2 剩下的 6 整段接上。结果 1 → 2 → 3 → 4 → 5 → 6 ✓。

复杂度：两个指针各自最多走一遍自己的链表，时间 O(m+n)（m、n 分别是两条链的长度）；只用了 dummy、tail 两个额外结点/指针，空间 O(1)。

为什么它就是满分解 ​

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

  1. 有没有重复扫描？ 没有。每个结点只被访问一次，接入结果链后就不再回头处理。
  2. 有没有重算已知的东西？ 没有。每一步的比较只依赖 l1、l2 当前指针的值，不需要重新计算任何已经确定的信息。
  3. 有没有放着性质不用？ 没有。两条链各自升序这个性质，正好被「谁小谁前进」的归并规则直接利用——这正是归并排序合并阶段的原理。

更根本的一条：合并两条链表，至少要把每个结点看一遍、接一遍——读一遍两条链表就是 O(m+n) 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

真正的难点在两处细节 ​

分不在优化上，在把两处边界写准：

  • 虚拟头结点省掉了「谁是第一个结点」的特殊判断。如果不用 dummy，需要单独处理「结果链为空时第一次挂结点」和「后续挂结点」两种情况；有了 dummy，tail 从一开始就有地方可挂，循环体里的逻辑完全统一。dummy 本身是栈上的局部变量，不需要 malloc，也不会被当成结果的一部分——返回的是 dummy.next，不是 &dummy。
  • 收尾时整段接上，而不是逐个结点接。循环退出时必有一条链走完、另一条链可能还剩一大段。tail->next = (l1 != NULL) ? l1 : l2 一步把剩下的整段接上，不需要再写一个循环去逐个搬。这是本题最容易画蛇添足的地方。
  • 相等值的归位：l1->val <= l2->val 用的是小于等于，值相等时优先取 l1 的结点。这不是唯一正确写法（取 l2 的结点同样正确），但落笔时要保证左右分支互斥、不遗漏也不重复处理某个结点。

一趟归并,看一遍 ​

用 l1 = 1 → 3 → 5、l2 = 2 → 4 → 6 演示——两个指针交替前进,谁小谁先接到结果链上:

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：

  • 想先把两条链表的值都收集起来再排序合并。这等于把「两条链各自有序」这个白送的性质丢掉,退化成对 m+n 个元素重新排序,时间从 O(m+n) 劣化到 O((m+n)log⁡(m+n)),还多付出一份数组空间——性质摆在那不用,反而更慢。
  • 想新建结点拼接结果链，而不是复用原结点。复用原结点（只改 next 指针）是本题的标准做法，额外分配 m+n 个新结点纯属浪费空间，原结点里的数据被原样保留，没有理由丢弃重建。

下一步 ​

相关真题（1题）

2017Q11选择题2分
去刷题

链式存储排序：链式存储对各排序算法效率的影响

单链表