#21

简单

高频

迭代法

合并两个有序链表

这是一道围绕链表、递归展开的高频练习。建议先掌握「迭代法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

递归

原题练习

题目分析

给你两条已经按升序排列好的链表，要求把它们合并成一条新的升序链表，并返回新链表的头节点。

合并过程中不能破坏“整体有序”这个条件。

一句话概括：

每一步都从两条链表当前头节点里选较小的那个，依次拼成新链表。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：用哑节点做结果链表头，始终把两个链表当前较小的节点接到尾部。

推荐代码

推荐解法：迭代法

时间复杂度： O(m+n)

空间复杂度： O(1)

核心思路：用哑节点做结果链表头，始终把两个链表当前较小的节点接到尾部。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建哑节点，简化边界情况处理
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        
        // 比较两个链表的节点，将较小的节点接到结果链表中
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        
        // 将剩余的节点接到结果链表中
        prev.next = list1 == null ? list2 : list1;
        
        return dummy.next;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用迭代法和哑节点，把两条有序链表像归并排序那样合并。

核心过程

先准备一个哑节点 dummy 和尾指针 tail。
循环比较两条链表当前头节点，把较小的那个接到结果尾部。
被接走的链表向前一步，tail 也同步向前。
当一条链表结束后，另一条剩余部分直接接到尾部。

复杂度总结

时间复杂度 O(m+n)，空间复杂度 O(1)。

面试补一句：哑节点是链表拼接题里最值得优先想到的稳定器。

核心思路

合并两个有序链表的关键不是“比较大小”，而是让指针移动过程稳定不丢链。哑节点负责统一处理头节点，尾指针负责持续向后拼接。

步骤讲解

先准备哑节点和尾指针

创建 dummy 作为结果链表的虚拟头节点，tail 指向当前结果尾部。

为什么这样做：这样就不需要单独处理第一个节点来自哪条链表。

对应代码提示：ListNode dummy = new ListNode(0); ListNode tail = dummy;

循环比较两条链表当前头节点

当两条链表都还没走完时，每次取值更小的那个节点接到 tail 后面。

为什么这样做：两条链表本身有序，只看当前头节点就足够决定下一个位置。

对应代码提示：if (list1.val <= list2.val) { ... } else { ... }

接完节点后同步推进指针

被接走的链表前进一步，结果链表尾指针也向后移动。

为什么这样做：只有两侧都同步推进，结果链表才会持续保持有序。

对应代码提示：tail = tail.next;

把剩余链表整体挂到尾部

当其中一条链表先耗尽时，另一条链表剩余部分可以直接接上。

为什么这样做：剩余部分本身已经有序，不需要再逐个比较。

对应代码提示：tail.next = list1 != null ? list1 : list2;

易错点

没有使用哑节点

这样会导致结果头节点需要单独分支处理，代码容易变乱。

正确理解：统一用 dummy 挂住结果开头。

忘记把剩余链表接上

循环退出后，另一条链表可能还有节点没处理。

正确理解：最后补一句 tail.next = ...。

移动顺序写乱导致断链

如果先推进了错误的指针，可能会跳过节点或丢掉链。

正确理解：固定顺序：先接节点，再移动被接走的链表，再移动 tail。

复杂度与适用判断

时间复杂度：O(m+n)

空间复杂度：O(1)

比其他方案更好在哪里：比递归法更省调用栈空间，面试手写也更稳。

适用判断：只要是“按顺序拼两条链表”，优先考虑哑节点 + 尾插。

额外提醒

链表合并题的稳定模板是 dummy + tail。

其他语言 / 其他解法

递归法

算法思路待补充

时间复杂度：O(?)

空间复杂度：O(?)

一句话思路：算法思路待补充

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

迭代法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表1值:链表2值:

准备就绪 - 输入两个链表值（用逗号分隔），然后点击开始

递归法动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

链表1值:链表2值:

准备就绪 - 输入两个链表值（用逗号分隔），然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。