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

约 5 分钟
文章信息 14 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 5-10 剑指 Offer 剑指 Offer（第 2 版） 字节 美团 京东 百度 快手 猿辅导
标签
链表 递归

题目描述

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

image-20261001230752548

image-20260928183452802

image-20260928183452803

题意分析

把两条按值非递减排列的单链表合并成一条同样有序的链表，返回合并后的头节点。两条输入链中的所有节点都要保留，相同值允许重复出现，不能像集合合并那样去重。

输入可能有一条为空，也可能两条都为空。下面复用已有节点，通过调整 next 重新连接结果，不为每个值重新创建节点；这会改变原来的链表连接关系。

解法：双指针归并链表

核心思路

[!blue]

用 l1 和 l2 指向两条链表中尚未合并部分的头节点。由于两条剩余链表各自有序，它们所有未处理节点中的最小值，必然就在这两个头节点中。因此每次比较头节点，将较小者接到结果尾部，就能确定下一个位置，无需搜索链表内部。

用哑节点 dummy 固定结果入口，tail 指向已经确定的结果前缀的最后一个节点。每次将选中的节点接到 tail.next，只推进被选中的输入指针，再让 tail 移到刚接入的节点。未选择的一侧保持原位置，留待下一轮比较。

从 dummy.next 到 tail 的这段已确定前缀始终有序，而且最后一个值不大于任一剩余候选头。初始前缀为空时成立；每次接入当前最小候选后仍然成立，因此反复选择不会破坏结果顺序。相等时优先选择第一条链表只是固定取舍，另一条的同值节点仍会在后续保留。

当一条链表耗尽，另一条剩余部分本身已经有序，所有值又不小于已经确定的尾节点，可以直接整段接上，不必再逐个访问。两条都为空时接上的也是空，返回 dummy.next 即可统一处理空结果。

解题步骤

  1. 创建哑节点 dummy，令结果尾指针 tail = dummy。
  2. 两条剩余链表都非空时比较头值；第一条较小或相等就接入 l1，否则接入 l2。
  3. 只将被选择的一条输入链向后推进，再将 tail 移到刚接入的节点。
  4. 任一输入链为空后，把另一条剩余链整体接到 tail.next。
  5. 返回 dummy.next，哑节点自身不属于答案。

代码实现

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)，其中 m、n 为两条输入链长度。每轮至少消耗一个节点，剩余链整体连接只需一次指针赋值。
  • 空间复杂度：O(1)。复用输入节点，只增加一个哑节点和常数个指针。

关键点总结

[!green]

  • 有序性把全体未处理节点的最小值限制在两个头节点中。
  • 结果前缀与剩余输入通过各自指针表示，选择哪一侧就只消耗哪一侧。
  • 剩余链已经满足排序关系，可以整体接尾，避免重复遍历。
  • 哑节点统一处理首次接入和空输入，不应出现在返回链中。

易错点总结

[!yellow]

  • 两个输入指针一起前进：每轮只接入一个节点，另一侧尚未选择的节点会被丢掉。
  • 接入后忘记移动 tail：下一轮会覆盖同一个后继位置，导致已接入节点丢失。
  • 相等时跳过其中一个节点：合并需要保留两个输入中的全部出现次数，不是去重。
  • 比较循环结束后直接返回：较长链表仍可能有未处理节点，应整体接到结果尾部。
  • 返回 dummy 而不是 dummy.next：会在答案前增加一个不属于输入的节点。
  • 把此实现当作保留原链的复制：它重新使用原节点并调整连接，调用后原链结构不保证保持原样。

相似题目

题目 难度 关联与区别
23. 合并 K 个升序链表 困难 两链表归并是合并k条链表的基础子过程，可按分治成对合并。
88. 合并两个有序数组 简单 同样从两个有序来源取下一项，数组版本需避免覆盖尚未读取的数据，常从末尾合并。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/12746570
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！