跳到主要内容

LeetCode 21. 合并两个有序链表

本节目标

用虚拟头节点和尾指针，把两条有序链表稳定地合并为一条。

这道题是链表解题框架的第二道母题。两条输入链表都已递增，当前需要决定的只有：谁是结果链表尚未填入部分中最小的节点。

查看原题

题意与约束​

给定两条按非递减顺序排列的单链表，把它们的原有节点重新连接成一条同样有序的链表。允许任一输入为空，节点值可以重复。

第一反应​

为结果建立栈上的虚拟头节点 dummy，让 tail 指向已合并部分的末尾。每轮比较两条链表的当前节点，连接较小者并推进它所在的输入指针。这样真正的结果头始终是 dummy.next，不必为第一个节点单独分支。

推导过程​

循环开始时，tail 前的节点已经构成正确的有序前缀，list1 与 list2 分别是两条输入中尚未合并的最小节点。选择较小者接到 tail 后不会破坏顺序；随后推进 tail，不变量继续成立。

当其中一条链表耗尽，另一条剩余部分本身已有序，且所有节点都不小于当前 tail，因此可以直接整体接上。

代码实现​

C++17
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 != nullptr ? list1 : list2;
        return dummy.next;
    }
};

复杂度分析​

  • 时间复杂度：O(m + n)，两条链表中的每个节点至多被比较、连接一次。
  • 空间复杂度：O(1)，只使用虚拟头节点和若干指针，复用输入节点。

常见误区​

  • 不使用虚拟头节点，导致第一次连接时需要额外判断结果头。
  • 循环结束后忘记连接未耗尽的一条链表。
  • 试图新建所有结果节点，既增加空间，也偏离了重连原节点的目标。

模式迁移​

两路合并时，每一路各暴露一个最小候选；迁移到合并 K 个升序链表后，用堆从 K 个当前候选中选择全局最小者。