0021. Merge Two Sorted Lists

题目信息

题号:
  1. 合并两个有序链表

难度:

Easy

主题:

链表、排序、归并、递归、双指针

原题:

LeetCode 0021

重点:

从收集全部节点重新排序,推导到只比较两个有序后缀的表头,并用尾指针原地完成两路归并

题目重述

给定两个按非递减顺序排列的单链表 list1 和 list2,把两条链表中的全部节点合并为一条同样按非递减 顺序排列的链表,并返回结果头节点。

两条输入链表都可能为空。结果必须保留所有节点,值相同的不同节点不能被合并或丢弃。题目允许修改原节点的 next 指针,因此可以直接复用输入节点,不需要为每个值创建新节点。两个当前节点值相等时,先接入任意一个 都不影响结果合法性。

链表节点总数位于 [0, 100],节点值位于 [-100, 100]。

自建示例

  • 交错取值:list1 = [1, 4, 7]、list2 = [2, 3, 8],返回 [1, 2, 3, 4, 7, 8];

  • 包含重复值:list1 = [1, 2, 2]、list2 = [1, 2, 5],返回 [1, 1, 2, 2, 2, 5];

  • 两侧长度不同:list1 = [-4, 6]、list2 = [-3, 0, 2, 9],返回 [-4, -3, 0, 2, 6, 9];

  • 一条链表为空:list1 = []、list2 = [-3, 0, 6],返回原第二条链表;

  • 两条链表都为空:list1 = []、list2 = [],返回空链表。

C++ 实现

#include <algorithm>
#include <vector>

// LeetCode 提供 ListNode 定义。
class Solution {
private:
    ListNode* collectAndSort(ListNode* first, ListNode* second) {
        std::vector<ListNode*> nodes;
        for (ListNode* node = first; node != nullptr; node = node->next) {
            nodes.push_back(node);
        }
        for (ListNode* node = second; node != nullptr; node = node->next) {
            nodes.push_back(node);
        }
        if (nodes.empty()) {
            return nullptr;
        }
        std::sort(nodes.begin(), nodes.end(), [](const ListNode* left, const ListNode* right) {
            return left->val < right->val;
        });
        for (int index = 1; index < static_cast<int>(nodes.size()); ++index) {
            nodes[index - 1]->next = nodes[index];
        }
        nodes.back()->next = nullptr;
        return nodes.front();
    }

    ListNode* recursiveMerge(ListNode* first, ListNode* second) {
        if (first == nullptr) {
            return second;
        }
        if (second == nullptr) {
            return first;
        }
        if (first->val <= second->val) {
            first->next = recursiveMerge(first->next, second);
            return first;
        }
        second->next = recursiveMerge(first, second->next);
        return second;
    }

    ListNode* iterativeMerge(ListNode* first, ListNode* second) {
        ListNode dummy;
        ListNode* tail = &dummy;
        while (first != nullptr && second != nullptr) {
            if (first->val <= second->val) {
                tail->next = first;
                first = first->next;
            } else {
                tail->next = second;
                second = second->next;
            }
            tail = tail->next;
        }
        tail->next = first != nullptr ? first : second;
        return dummy.next;
    }

public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        return iterativeMerge(list1, list2);
    }
};

题解

收集后重新排序

暂时不利用两条链表已经有序这一条件,可以先遍历它们,把全部节点指针放入数组,按节点值排序,再按照排序结果 重新设置每个节点的 next。collectAndSort 就是这种直接方法。

它不会遗漏节点:两个遍历把每个输入节点各收集一次,排序只改变指针在数组中的次序,最后按该次序重建一条链。 相同值的节点即使排序后先后次序不确定,也仍是两个独立指针,都会保留在结果中。

设总节点数为 N。收集和重连都是 O(N),排序需要 O(N log N),还要保存 N 个节点指针。 真正的浪费是:两个输入内部的大小关系原本已经全部确定,这种方法却把这些信息丢掉,再对所有节点做一次通用排序。

有序后缀

遍历过程中,first 与 second 分别指向两条链表尚未处理的后缀。因为每个后缀仍按非递减顺序排列, 后缀最小值必定位于它的表头。

因此,全体未处理节点中的最小值不需要从 N 个节点中重新搜索,只可能是以下两个候选之一:

  • first 指向的节点;

  • second 指向的节点。

若 first->val <= second->val,则 first 不大于第二条链表的表头,而第二条链表中的其他节点又都不小于 自己的表头,所以 first 不大于任何未处理节点,可以安全接入结果。另一种情况完全对称。

接入一个表头后只推进对应指针。被推进链表的剩余部分仍然有序,另一条链表没有变化,于是同样的两个候选模型 在下一轮自动恢复。通用排序因此被替换为一次从左到右的两路归并。

状态演化

以 list1 = [1, 4, 7]、list2 = [2, 3, 8] 为例:

first

second

本轮选择

已完成前缀

1

2

1

1

4

2

2

1 -> 2

4

3

3

1 -> 2 -> 3

4

8

4

1 -> 2 -> 3 -> 4

7

8

7

1 -> 2 -> 3 -> 4 -> 7

空

8

整体接入第二条后缀

1 -> 2 -> 3 -> 4 -> 7 -> 8

每次比较只确定结果中的下一个节点,不需要提前知道后续节点的完整交错次序。

递归分解

若两条链表都非空,两个表头中的较小者已经能够确定为当前结果的首节点。假设 first 较小,则剩余答案是 first->next 与 second 的合并结果:

first -> merge(first.next, second)

recursiveMerge 直接按照这个定义改写 first->next,并返回 first。若任一链表为空,另一条链表本身 已经有序,可以直接返回,既是递归终点,也是剩余后缀整体接入的情况。

递归每层确定一个结果节点,代码紧贴问题分解。不过相邻层只需要记住“当前选中了哪个节点以及剩余两个表头”, 调用栈最坏仍会为每个节点保存一层状态。算法的选择规则已经足够简单,可以改用显式指针顺序执行。

尾指针归并

iterativeMerge 用 tail 指向已完成结果的最后一个节点。每轮比较两个表头,把较小节点接到 tail->next,推进对应输入指针,再让 tail 移到新接入节点。

循环开始时保持三个事实:

  • dummy.next 到 tail 是已经确定的非递减结果前缀;

  • 该前缀恰好包含两个输入中已经越过的节点,每个节点出现一次;

  • first 与 second 指向两个尚未处理的有序后缀。

本轮选中的表头是全部未处理节点中的最小值,所以它不会破坏结果前缀的顺序。只推进被选中的输入指针后,已处理 节点和两个未处理后缀仍然互不重叠,循环状态继续成立。

虚拟头节点

结果开始时没有真实头节点。若直接维护 head 与 tail,第一次选中节点时需要同时初始化二者,后续才能 统一使用 tail->next。

虚拟节点 dummy 预先提供一个固定前驱,使第一次和之后的接入都执行相同操作。它本身不属于结果,最终返回 dummy.next。两条输入都为空时,循环不会执行,dummy.next 自然为 nullptr。

剩余后缀

主循环在至少一条链表为空时停止。此时另一条链表的剩余部分本身已经有序。若结果前缀非空,它的表头也不小于 结果尾值;否则它应在上一轮被选择。若结果前缀为空,说明至少一条输入从开始就为空,非空链表可以直接作为结果。

所以只需执行一次 tail->next = first != nullptr ? first : second,把完整后缀接入结果。逐节点继续循环虽然 也能得到正确答案,却会重复执行已经不再需要的空指针判断和尾指针移动。

代码演进

collectAndSort 收集全部节点并重新排序。它不利用输入链表内部已经存在的顺序,需要节点数组、通用排序和完整 重连。

识别出每个未处理后缀的最小值就是表头后,候选集合从全部剩余节点缩减为两个表头。recursiveMerge 删除节点 数组和排序过程,每层只选择一个表头,再递归合并剩余后缀。

iterativeMerge 保留相同的表头选择,使用 tail 和两个输入指针替代递归调用栈。虚拟头节点又删除了首次 接入的特殊分支;某侧耗尽后,剩余有序后缀通过一次链接整体接入。

公开入口采用 iterativeMerge。它复用输入节点,在保持线性时间的同时只使用常数工作空间。

复杂度分析

方法

时间复杂度

工作空间

主要代价

收集后排序

O((m+n) log(m+n))

O(m+n)

保存全部节点指针并进行通用排序

递归归并

O(m+n)

O(m+n)

每个节点选择一次,空间来自递归调用栈

迭代归并

O(m+n)

O(1)

每个节点最多作为表头参与一次选择

设两条链表长度分别为 m 和 n。三种方法都复用原节点,返回链表本身不计入工作空间。迭代方法在一侧 耗尽后直接接入剩余后缀,因此其中部分节点甚至不再需要逐个比较。