在数据结构与算法的学习中，链表是基础且重要的结构之一，而“合并两个有序链表”则是链表操作里的经典问题——它不仅频繁出现在面试题中，更能帮我们深化对链表遍历、指针操作的理解。今天，我们就从问题定义出发，一步步拆解思路，再到代码实现与优化，彻底搞懂这个问题。

一、问题定义：明确我们要解决什么

首先得把问题说清楚，避免理解偏差。题目要求如下：

         给定两个升序排列的有序链表（链表1和链表2），将它们合并成一个新的升序链表。新链表是通过拼接两个链表的所有节点组成的，要求不能创建新的节点（仅复用原节点），且时间复杂度尽可能优化。

举个直观的例子：

链表1：1 → 3 → 5 → null

链表2：2 → 4 → 6 → null

合并后结果：1 → 2 → 3 → 4 → 5 → 6 → null

这里要注意两个关键点：一是“升序”要求，合并后必须保持有序；二是“复用原节点”，不能额外开辟节点空间，这是空间优化的核心点。

二、核心思路：如何“有序拼接”？

       既然两个链表本身是有序的，我们就不需要像“合并两个无序链表”那样先遍历存数据再排序——那样的时间复杂度是O(nlogn)，不够高效。利用“有序”的特性，我们可以用“双指针遍历”的思路实现O(n+m)的时间复杂度（n、m分别为两个链表的长度）。

具体思路可以类比“整理两堆有序的卡片”：

1. 拿两个指针，分别指向两个链表的头节点（p1指向链表1头，p2指向链表2头）；

2. 比较p1和p2指向的节点值，把值小的节点接到新链表的末尾；

3. 把值小的那个指针向后移动一步（比如p1值小，p1就移到下一个节点）；

4. 重复步骤2-3，直到其中一个指针走到链表末尾（指向null）；

5. 把另一个没走完的链表剩下的节点，直接接到新链表末尾（因为剩下的节点本身是有序的）。

       这里还有个小细节：新链表的头节点不好直接确定（可能是链表1的头，也可能是链表2的头），所以通常会创建一个“虚拟头节点”（dummy node）——它不存储实际数据，只是用来方便地定位新链表的头，最后返回虚拟头节点的下一个节点即可。

三、代码实现：迭代法与递归法

       基于上面的思路，有两种常见的实现方式：迭代法（更直观，易理解）和递归法（代码更简洁，考验递归思维）。我们以Java语言为例，结合单向链表的定义来实现。

首先定义链表节点结构：

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; }
}

1. 迭代法：直观的双指针操作

按照前面的“整理卡片”思路，用迭代的方式一步步拼接，代码逻辑清晰，适合初学者：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 1. 创建虚拟头节点，方便后续拼接
    ListNode dummy = new ListNode(-1);
    // 2. 定义一个指针cur，指向新链表的末尾（初始指向虚拟头）
    ListNode cur = dummy;
    // 3. 双指针遍历两个链表，直到其中一个遍历完
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            // 把list1的节点接到新链表末尾
            cur.next = list1;
            // list1指针后移
            list1 = list1.next;
        } else {
            // 把list2的节点接到新链表末尾
            cur.next = list2;
            // list2指针后移
            list2 = list2.next;
        }
        // 新链表末尾指针后移
        cur = cur.next;
    }
    // 4. 把剩下的节点直接接到新链表末尾
    cur.next = list1 != null ? list1 : list2;
    // 5. 返回虚拟头的下一个节点（真正的头节点）
    return dummy.next;
}

迭代法的逻辑拆解：

• 虚拟头节点dummy的val设为-1（无实际意义，只要是int值即可），cur指针负责“拼接节点”；

• while循环的条件是“两个链表都没遍历完”，一旦其中一个为null，循环就结束；

• 循环内比较两个节点值，谁小就接谁，然后对应的指针后移；

• 循环结束后，剩下的节点必然是有序的，直接接在cur后面即可；

• 最后返回dummy.next，就是合并后的新链表头。

2. 递归法：利用递归的“子问题”思想

       递归的核心是“把大问题拆成小问题”。合并两个有序链表的大问题，可以拆成：“找到当前两个节点中较小的那个，然后合并剩下的链表”。

递归思路：

1. 终止条件：如果其中一个链表为null，返回另一个链表（剩下的节点直接用）；

2. 递归逻辑：比较两个链表的头节点，假设list1.val更小，那么list1的next就应该是“list1.next和list2合并后的结果”，然后返回list1；反之同理。

递归实现代码：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 终止条件：其中一个链表为空，返回另一个
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    // 递归逻辑：选较小的节点，然后合并剩下的
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

递归法的理解难点：

很多人刚开始看递归代码会觉得“绕”，其实可以用前面的例子代入：

list1=1→3→5，list2=2→4→6

• 第一次调用：1<2，所以list1.next = 合并(3→5, 2→4→6)，然后返回1；

• 第二次调用（合并3→5和2→4→6）：2<3，所以list2.next = 合并(3→5, 4→6)，返回2；

• 第三次调用（合并3→5和4→6）：3<4，所以list1.next = 合并(5, 4→6)，返回3；

• 第四次调用（合并5和4→6）：4<5，所以list2.next = 合并(5, 6)，返回4；

• 第五次调用（合并5和6）：5<6，所以list1.next = 合并(null, 6)，返回5；

• 第六次调用（合并null和6）：返回6，递归终止；

• 反向拼接：5.next=6 → 4.next=5 → 3.next=4 → 2.next=3 → 1.next=2，最终得到1→2→3→4→5→6。

       递归法的优点是代码简洁，但要注意递归深度——如果两个链表都很长（比如长度1e4），会导致栈溢出（递归深度超过JVM的栈容量），所以实际开发中迭代法更稳妥。

四、复杂度分析：看看我们的代码效率如何

无论是迭代法还是递归法，核心都是“遍历两个链表各一次”，所以复杂度分析是一致的：

1. 时间复杂度：O(n+m)，其中n是list1的长度，m是list2的长度。因为每个节点只被遍历一次，没有多余的操作；

2. 空间复杂度：迭代法是O(1)，只用到了dummy和cur两个额外指针，没有开辟新的空间；递归法是O(n+m)，因为递归调用会占用栈空间，栈深度最大为n+m（最坏情况是两个链表依次交替，递归到最后一个节点）。

       面试中如果被问到“如何优化空间复杂度”，要能说出“用迭代法替代递归法，将空间复杂度从O(n+m)降为O(1)”。

五、常见问题与边界情况

写代码时，边界情况往往是出错的重灾区，合并两个有序链表的常见边界情况有3种，一定要覆盖到：

1. 其中一个链表为空：比如list1为null，直接返回list2；反之同理。前面的代码已经通过终止条件或最后一步拼接覆盖了这种情况；

2. 两个链表都为空：此时dummy.next为null，返回null，符合预期；

3. 一个链表是另一个链表的“子集”：比如list1=1→3→5，list2=2→4，合并后1→2→3→4→5；或者list1=1→2→3，list2=4→5→6，合并后1→2→3→4→5→6。迭代法的while循环和最后一步拼接能处理这种情况。

建议写代码后，用这几种边界情况做测试，确保代码的健壮性。

六、总结：关键知识点回顾

合并两个有序链表虽然是基础题，但包含了很多链表操作的核心思想，总结一下关键点：

• 核心思路：利用“有序”特性，双指针遍历拼接，避免额外排序；

• 实现方式：迭代法（直观、空间O(1)）和递归法（简洁、空间O(n+m)）；

• 技巧：用虚拟头节点简化头节点定位；

• 边界：覆盖“空链表”“子集链表”等情况。

       这个问题的思路可以推广到“合并k个有序链表”（力扣23题），核心还是“利用有序特性，逐步合并”——比如先合并前两个，再用结果合并第三个，或者用优先队列优化。掌握了两个的合并，k个的合并也就水到渠成了。

如果觉得有收获，欢迎点赞收藏，也可以在评论区分享你的学习心得或疑问～