百卷

外观

21. 合并两个有序链表

约 5904 字大约 20 分钟

链表递归双指针

2025-05-13

LeetCode原题链接

原题

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2： 输入：l1 = [], l2 = [] 输出：[]

示例 3： 输入：l1 = [], l2 = [0] 输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

在实际开发中，我们经常需要处理有序数据的合并操作。合并两个有序链表是一个经典的数据结构问题，它不仅是面试中的常见题目，也反映了软件工程中的实际应用场景。

链表作为一种基础数据结构，在许多系统中都有广泛应用。例如，在数据库系统中，合并有序链表可以用于归并排序的实现；在操作系统的内存管理中，空闲内存块的管理也可能涉及类似的合并操作；在分布式系统中，不同节点的有序数据合并也是常见需求。

这个问题的核心在于如何高效地将两个已排序的链表合并成一个新的有序链表。虽然问题描述简单，但它考察了候选人对链表操作的基本理解、指针操作的熟练程度，以及解决问题的逻辑思维能力。

掌握这个问题的解法，不仅有助于我们应对面试，更能帮助我们在实际工作中更好地处理类似的数据合并需求。

审题

在面试中，拿到这道题后，我们首先应该与面试官确认一些关键信息，以确保我们理解题目要求并考虑到所有可能的情况。

候选人：这道题是要合并两个已排序的链表，对吗？我想确认一下输入和输出的具体要求。

面试官：是的，你需要将两个已经按升序排列的链表合并成一个新的升序链表。

候选人：关于链表节点的定义，我看到题目中给出了ListNode的结构，每个节点包含一个整数值和指向下一个节点的指针，对吗？

面试官：是的，链表节点的定义已经给出，你不需要自己定义。

候选人：输入是两个链表的头节点，输出应该是合并后的新链表的头节点，对吗？

面试官：正确。

候选人：我注意到题目中提到链表节点数目范围是[0, 50]，这意味着链表可能为空。当一个或两个链表为空时，我应该如何处理？

面试官：这是个好问题。如果其中一个链表为空，你应该直接返回另一个链表；如果两个链表都为空，则返回空链表。

候选人：节点值的范围是-100到100，这个信息对解题有影响吗？

面试官：这个范围主要是为了限定测试用例，对于算法实现本身没有特别的影响，因为我们只需要比较节点值的大小，而不关心具体的值域。

候选人：题目要求合并为一个"新的"链表，这是否意味着我需要创建新的节点，而不是直接修改原有链表的指针？

面试官：不，你不需要创建新节点。"新的"链表指的是通过重新连接原有两个链表的节点形成的链表。你应该通过调整节点的next指针来完成合并，而不是创建新节点。

候选人：最后，关于时间和空间复杂度的要求，有什么特别的限制吗？

面试官：我们期望你能提供一个时间复杂度为O(n+m)的解法，其中n和m分别是两个链表的长度。空间复杂度应该是O(1)，即只使用常量额外空间。

候选人：好的，我理解了题目要求。我将实现一个函数，接收两个已排序链表的头节点，通过调整指针将它们合并成一个新的有序链表，并返回合并后链表的头节点。我会特别注意处理空链表的情况，并确保算法的时间复杂度为O(n+m)，空间复杂度为O(1)。

解析

思路概述

合并两个有序链表是一个经典的链表操作问题。由于两个输入链表已经是有序的（升序），我们可以利用这一特性，通过比较两个链表当前节点的值，每次选择值较小的节点加入到结果链表中，然后移动指针到下一个节点，重复这个过程直到至少一个链表被遍历完。

这个问题有两种常见的解法：迭代法和递归法。我们将主要讨论迭代法，因为它更直观且在实际工作中使用更广泛，但也会简要介绍递归解法。

迭代法思路

迭代法的核心思想是：

  1. 创建一个哑节点（dummy node）作为结果链表的头部，这样可以简化边界情况的处理
  2. 维护一个指针 current，指向当前结果链表的末尾
  3. 比较两个链表当前节点的值，将较小值的节点接到 current 后面，并更新对应链表的指针
  4. 重复步骤3，直到至少一个链表为空
  5. 将剩余非空链表直接接到结果链表的末尾
  6. 返回哑节点的下一个节点，即结果链表的真正头节点

图示说明

假设我们有两个链表：

  • list1: 1 -> 2 -> 4
  • list2: 1 -> 3 -> 4

合并过程如下：

  1. 初始状态：

    dummy -> null
current = dummy
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

  2. 比较 list1[0] 和 list2[0]，两者都是1，选择 list1 的节点（也可以选择 list2）：

    dummy -> 1 -> null
current = 1
list1: 2 -> 4
list2: 1 -> 3 -> 4

  3. 比较 list1[0] (2) 和 list2[0] (1)，选择 list2 的节点：

    dummy -> 1 -> 1 -> null
current = 1 (第二个1)
list1: 2 -> 4
list2: 3 -> 4

  4. 比较 list1[0] (2) 和 list2[0] (3)，选择 list1 的节点：

    dummy -> 1 -> 1 -> 2 -> null
current = 2
list1: 4
list2: 3 -> 4

  5. 比较 list1[0] (4) 和 list2[0] (3)，选择 list2 的节点：

    dummy -> 1 -> 1 -> 2 -> 3 -> null
current = 3
list1: 4
list2: 4

  6. 比较 list1[0] (4) 和 list2[0] (4)，两者相等，选择 list1 的节点：

    dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> null
current = 4
list1: null
list2: 4

  7. list1 已经为空，将 list2 剩余部分接到结果链表末尾：

    dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

  8. 返回 dummy.next，即结果链表的头节点：

    1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null

递归法思路

递归法的思路更为简洁，但可能不太直观：

  1. 基本情况：如果其中一个链表为空，返回另一个链表
  2. 比较两个链表当前头节点的值
  3. 选择值较小的节点作为当前结果节点
  4. 递归地将该节点的next指向合并剩余部分的结果
  5. 返回当前结果节点

递归法的优点是代码简洁，但在链表很长的情况下可能导致栈溢出，因此在实际工作中，迭代法通常是更可靠的选择。

算法步骤（迭代法）

  1. 创建一个哑节点 dummy，用于简化边界情况处理
  2. 创建一个指针 current，初始指向 dummy
  3. 当 list1 和 list2 都不为空时： a. 比较 list1.val 和 list2.val b. 如果 list1.val <= list2.val，则 current.next = list1，并将 list1 前进一步 c. 否则，current.next = list2，并将 list2 前进一步 d. 将 current 前进一步
  4. 检查是否有剩余链表： a. 如果 list1 不为空，则 current.next = list1 b. 如果 list2 不为空，则 current.next = list2
  5. 返回 dummy.next，即合并后链表的头节点

源码

核心代码模式

Java
/**
 * 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(-1);
        // 当前指针，用于构建新链表
        ListNode current = dummy;
        
        // 当两个链表都不为空时，比较节点值并合并
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                // 如果list1当前节点值小于等于list2，选择list1节点
                current.next = list1;
                list1 = list1.next;
            } else {
                // 否则选择list2节点
                current.next = list2;
                list2 = list2.next;
            }
            // 移动当前指针
            current = current.next;
        }
        
        // 处理剩余节点
        // 如果list1还有剩余，直接接到结果链表末尾
        if (list1 != null) {
            current.next = list1;
        }
        // 如果list2还有剩余，直接接到结果链表末尾
        if (list2 != null) {
            current.next = list2;
        }
        
        // 返回合并后的链表头节点（跳过哑节点）
        return dummy.next;
    }
}

ACM模式

Java
import java.util.*;

// 链表节点定义
class ListNode {
    int val;
    ListNode next;
    
    ListNode() {}
    
    ListNode(int val) { 
        this.val = val; 
    }
    
    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
}

public class Main {
    // 合并两个有序链表的函数
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建哑节点作为合并链表的起点
        ListNode dummy = new ListNode(-1);
        // 当前指针，用于构建新链表
        ListNode current = dummy;
        
        // 当两个链表都不为空时，比较节点值并合并
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                // 如果list1当前节点值小于等于list2，选择list1节点
                current.next = list1;
                list1 = list1.next;
            } else {
                // 否则选择list2节点
                current.next = list2;
                list2 = list2.next;
            }
            // 移动当前指针
            current = current.next;
        }
        
        // 处理剩余节点
        // 如果list1还有剩余，直接接到结果链表末尾
        if (list1 != null) {
            current.next = list1;
        }
        // 如果list2还有剩余，直接接到结果链表末尾
        if (list2 != null) {
            current.next = list2;
        }
        
        // 返回合并后的链表头节点（跳过哑节点）
        return dummy.next;
    }
    
    // 从数组创建链表的辅助函数
    public static ListNode createLinkedList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        for (int val : arr) {
            current.next = new ListNode(val);
            current = current.next;
        }
        
        return dummy.next;
    }
    
    // 打印链表的辅助函数
    public static void printLinkedList(ListNode head) {
        List<Integer> result = new ArrayList<>();
        while (head != null) {
            result.add(head.val);
            head = head.next;
        }
        System.out.println(result);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取第一个链表
        String line1 = scanner.nextLine().trim();
        line1 = line1.substring(1, line1.length() - 1); // 去掉方括号
        String[] strArr1 = line1.isEmpty() ? new String[0] : line1.split(",");
        int[] arr1 = new int[strArr1.length];
        for (int i = 0; i < strArr1.length; i++) {
            arr1[i] = Integer.parseInt(strArr1[i].trim());
        }
        
        // 读取第二个链表
        String line2 = scanner.nextLine().trim();
        line2 = line2.substring(1, line2.length() - 1); // 去掉方括号
        String[] strArr2 = line2.isEmpty() ? new String[0] : line2.split(",");
        int[] arr2 = new int[strArr2.length];
        for (int i = 0; i < strArr2.length; i++) {
            arr2[i] = Integer.parseInt(strArr2[i].trim());
        }
        
        // 创建链表
        ListNode list1 = createLinkedList(arr1);
        ListNode list2 = createLinkedList(arr2);
        
        // 合并链表
        ListNode mergedList = mergeTwoLists(list1, list2);
        
        // 打印结果
        printLinkedList(mergedList);
        
        scanner.close();
    }
}

吊打面试官

在面试中，解决问题只是第一步，更重要的是展示你对问题的深入理解。以下是面试官可能会问到的问题及其答案：

问题1：该算法的时间复杂度和空间复杂度是多少？如何计算的？

答案：

时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度。

分析：在迭代解法中，我们最多遍历两个链表各一次。在最坏情况下，我们需要遍历完两个链表的所有节点才能完成合并。因此，总的时间复杂度是 O(n + m)。

空间复杂度：O(1)。

分析：我们只使用了常量级的额外空间（几个指针变量），不会随着输入规模的增加而增加。虽然我们创建了一个哑节点（dummy node），但这只是一个常量级的空间开销。需要注意的是，我们没有创建新的链表节点，而是通过调整原有节点的指针来构建结果链表，因此不需要额外的空间来存储合并后的链表。

递归解法的空间复杂度是 O(n + m)，因为递归调用栈的深度最多为 n + m。这也是为什么在实际工程中，我们通常更倾向于使用迭代解法。

问题2：如果输入的链表非常长，你的算法会有什么问题？有没有优化空间？

答案：

对于非常长的链表，迭代解法依然能够高效工作，因为它的时间复杂度是线性的，空间复杂度是常量级的。

然而，如果使用递归解法，当链表非常长时，可能会导致栈溢出（Stack Overflow）问题，因为递归深度与链表长度成正比。

优化方案：

  1. 坚持使用迭代解法，避免递归带来的栈溢出风险。
  2. 如果必须使用递归，可以考虑尾递归优化（虽然大多数语言的编译器不一定支持）。
  3. 在某些特殊场景下，可以考虑分块处理：先将长链表分成多个小块，分别合并后再连接起来，这样可以减少单次递归的深度。

在实际工程中，我们通常会选择迭代解法，因为它更可靠，尤其是在处理大规模数据时。

问题3：如果要合并k个有序链表，你会如何扩展这个算法？

答案：

合并k个有序链表是LeetCode第23题"合并K个升序链表"，是本题的扩展。有几种常见的解法：

  1. 顺序合并：

    • 使用当前的mergeTwoLists函数，依次合并每个链表。
    • 时间复杂度：O(kN)，其中k是链表数量，N是所有链表的总节点数。
    • 这种方法简单但效率较低，因为第一个链表会被合并k-1次。

  2. 分治合并：

    • 将k个链表分成两半，分别合并，然后再合并结果。
    • 时间复杂度：O(N log k)
    • 空间复杂度：O(log k)，递归深度
    • 这种方法更高效，因为每个链表只会被合并log k次。

  3. 优先队列（最小堆）：

    • 创建一个最小堆，初始包含所有链表的头节点。
    • 每次从堆中取出最小节点，加入结果链表，并将该节点的下一个节点加入堆中。
    • 时间复杂度：O(N log k)
    • 空间复杂度：O(k)
    • 这种方法在实际工程中很常用，尤其是当k很大时。

在实际工作中，我会根据具体情况选择合适的方法：

  • 如果k较小（如k=2或3），简单的顺序合并可能就足够了。
  • 如果k较大，我会优先考虑优先队列方法，因为它实现简单且效率高。
  • 如果对空间要求严格，分治合并可能是更好的选择。

这个问题很好地展示了如何将基本算法扩展到更复杂的场景，以及如何在时间和空间效率之间做权衡。

结语

合并两个有序链表是一个经典的数据结构问题，它不仅是算法面试的常客，也是我们理解链表操作和指针操作的基础。通过这道题目，我们可以学习到几个重要的编程思想：

首先，哑节点（dummy node）的使用是处理链表问题的一个常见技巧。它帮助我们简化了边界情况的处理，尤其是当需要修改头节点时。在实际开发中，这种技巧可以让我们的代码更加简洁和健壮。

其次，这道题展示了迭代与递归两种不同的问题解决思路。迭代解法通常更为直观，且在处理大规模数据时更加高效；而递归解法则更为简洁，但需要注意栈溢出的风险。在实际工作中，我们需要根据具体场景选择合适的方法。

第三，这道题目虽然简单，但它是许多更复杂问题的基础。例如，合并K个有序链表、合并区间等问题都可以看作是这个基本问题的扩展。掌握这个基础问题，有助于我们解决更复杂的算法挑战。

最后，这道题目也提醒我们，在面试和实际工作中，不仅要关注算法的正确性，还要考虑其效率和可扩展性。一个好的解决方案应该在时间复杂度、空间复杂度和代码可读性之间取得平衡。

总的来说，合并两个有序链表是一个看似简单但内涵丰富的问题。通过深入理解这个问题，我们不仅能够在面试中表现出色，更能够在实际工作中写出更高质量的代码。