LeetCode 21. 合并两个有序链表

约 5 分钟
文章信息 27 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 历史考题 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 旷视 亚马逊 虾皮 携程 LeetCode 热题 100 面试经典 150 题
标签
链表 递归
目录

题目描述

✅ 21. 合并两个有序链表

image-20230723230152896

image-20230723230201105

题意分析

给定两条各自已经升序的单链表 list1 和 list2，要求把它们的全部节点重新串成一条升序链表，返回新链表的头节点。输出的节点集合就是输入的节点集合，不多不少。

「两条链表各自已经升序」是本题最关键的前提，它带来两条可以直接使用的结论。第一，每条链表当前的头节点就是这条链表剩下所有节点里的最小值，所以判断「整体的下一个最小值是谁」时，只需要看两个头节点，不必往后扫。第二，一旦有一条链表被取空，另一条链表剩下的那一整段本身就是有序的，可以整段接过去，不需要再逐个比较。

题面要求「拼接所有节点」，暗示的是复用原有节点，只改 next 指针，不新建节点。如果每步都 new 一个新节点，值虽然也对，但会额外花掉与节点总数同阶的空间，同时也失去了链表题真正想考的东西：能不能把指针的重连顺序想清楚。复用节点的代价是结果链表与输入链表共享内存，原链表在函数返回后已经被破坏，这一点面试里最好主动说明。

需要留意的边界情形有：两条链表都为空，此时应返回空；只有一条为空，此时应原样返回另一条；两条长度悬殊，短的一条会先被取空；两条里存在相等的值，此时必须保证相等的值不会被丢掉，也不会被重复接入；只剩一条链表时，不要再进入比较逻辑，否则会去访问空指针的字段。

还有一个容易被忽略的困难：结果链表的头节点是谁，在开始比较之前是未知的，它既可能来自 list1 也可能来自 list2。如果直接拿「结果头指针」当游标去往后接，就要先分一次叉决定它的初值，之后每接一个节点又要判断「现在是不是第一个节点」，特判会散落在整段代码里。

解法：哨兵节点迭代合并

核心思路

用哨兵节点统一处理结果链表的头部，tail 始终指向已合并部分的尾节点。每次接入两个当前节点中较小的一个；某条链表耗尽后，直接接上另一条的剩余部分。

解题步骤

  1. 创建哨兵节点 dummy，令 tail = dummy。
  2. 两条链表都非空时，比较头节点并接入较小者。
  3. 移动被接入链表的指针和 tail。
  4. 循环结束后接上剩余链表，返回 dummy.next。

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        tail.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(m + n)$。
  • 空间复杂度：$O(1)$，复用原链表节点。

关键点总结

  • 哨兵节点避免单独处理结果头节点。
  • 循环条件必须是两条链表都非空。
  • 一条链表耗尽后，可直接挂接另一条的剩余部分。

易错点总结

  • 返回 dummy 或 tail，正确结果头是 dummy.next。
  • 接入节点后忘记移动对应链表指针或 tail。
  • 循环条件写成“或”，导致访问空指针。
  • 忘记接上未耗尽链表的剩余部分。

相似题目

题目 难度 考察点
23. 合并 K 个升序链表 困难 从两条扩到 K 条，需要用最小堆维护 K 个头节点，或分治地反复调用本题的两两合并
LCR 078. 合并 K 个升序链表 困难 与 23 题同题的 LCR 版本，可以把本题函数原封不动当作子过程复用
剑指 Offer 25. 合并两个排序的链表 简单 与本题完全同题，仅函数签名和题面表述不同，可直接套同一份代码
88. 合并两个有序数组 简单 载体换成数组且要原地写回 nums1，正序填会覆盖未处理元素，需改为从后往前填
面试题 10.01. 合并排序的数组 简单 与 88 题同型的数组原地合并，同样靠倒序填充规避覆盖，没有指针重连问题
148. 排序链表 中等 输入不再有序，要先用快慢指针把链表断成两半，再拿本题的合并做归并排序的合并步
LCR 077. 排序链表 中等 与 148 题同题，同样把本题当作归并排序的最后一步
2. 两数相加 中等 同为双指针并行走两条链表 + 哨兵建结果，但要新建节点并维护进位，且一条走完后不能整段挂接
1669. 合并两个链表 中等 不比较大小，而是按下标把一段整体替换掉，考的是找到两个断点并正确接线