引言

合并有序链表是算法领域的经典问题，常见于面试题和实际工程场景。本文从基础问题合并两个有序链表出发，逐步深入探讨更复杂的合并K个有序链表问题。通过对比不同解法的实现原理、时间/空间复杂度及适用场景，帮助读者全面掌握链表合并的核心技巧。

---

一、合并两个有序链表

问题描述

给定两个升序排列的链表，将它们合并为一个新的升序链表并返回头节点。

方法一：递归法

class Solution {
    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;
        }
    }
}

核心思想：

• 分治策略：每次递归选择较小的头节点，将剩余部分继续合并
• 终止条件：任一链表为空时返回另一链表

复杂度分析：

• 时间复杂度：O(n + m)（n、m为两链表长度）
• 空间复杂度：O(n + m)（递归栈深度）

适用场景：

• 链表较短时（递归深度可控）
• 需要代码简洁性的场景

---

方法二：迭代法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

核心思想：

• 哑节点技巧：使用虚拟头节点统一处理边界
• 双指针遍历：逐步连接较小节点

复杂度分析：

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

适用场景：

• 处理大规模数据（无栈溢出风险）
• 需要稳定性的生产环境

---

二、合并K个有序链表

问题描述

将K个升序链表合并为一个新的升序链表并返回头节点。

方法一：分治法（最优解）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2); // 复用迭代合并方法
    }
}

核心思想：

• 二分合并：将K个链表拆分为两半递归处理，逐层合并结果
• 复用双链表合并：使用迭代法合并两个链表

复杂度分析：

• 时间复杂度：O(NlogK)（N为总节点数）
• 空间复杂度：O(logK)（递归栈深度）

优势：

• 时间复杂度最优
• 避免栈溢出风险

---

方法二：逐对顺序合并法（低效）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode result = lists[0];
        for (int i = 1; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]); // 递归合并
        }
        return result;
    }
}

核心缺陷：

• 时间复杂度：O(K²N)（K为链表数，N为平均长度）
• 空间风险：递归合并导致栈深度达O(KN)，可能溢出

对比测试（假设每个链表长度N=1000）：

K值	分治法操作次数	顺序合并法操作次数
10	~33,000	~55,000
100	~664,000	~5,050,000
1000	~9,966,000	~500,500,000

---

方法三：优先队列法（备选方案）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!pq.isEmpty()) {
            ListNode min = pq.poll();
            cur.next = min;
            cur = cur.next;
            if (min.next != null) pq.offer(min.next);
        }
        return dummy.next;
    }
}

复杂度分析：

• 时间复杂度：O(NlogK)
• 空间复杂度：O(K)（堆空间）

适用场景：

• 链表数量较小时
• 需要代码简洁性时

---

三、方法对比与选型建议

方法	时间复杂度	空间复杂度	优点	缺点
分治法	O(NlogK)	O(logK)	时间最优，空间安全	代码实现稍复杂
优先队列法	O(NlogK)	O(K)	代码简洁	堆空间消耗大
顺序合并法	O(K²N)	O(KN)	实现简单	性能差，易栈溢出

选型建议：

1. 生产环境优先选择分治法：兼顾时间效率和空间安全性
2. 小规模数据可用优先队列法：代码更简洁直观
3. 避免使用顺序合并法：仅用于理解问题本质

---

四、高频面试考点

1. 递归与迭代的选择依据

   • 递归：链表长度小时使用（代码简洁）
   • 迭代：处理长链表或不确定长度时使用

2. 分治法的分治策略

   • 二分合并减少重复遍历
   • 与归并排序的相似性

3. 哑节点(Dummy Node)的作用

   • 统一处理头节点不确定的情况
   • 简化指针操作

---

五、最佳实践总结

1. 合并两个链表时：

   • 优先使用迭代法保证稳定性
   • 递归法可用于代码简洁性优先的场景

2. 合并K个链表时：

   • 默认使用分治法（LeetCode官方推荐解法）
   • 当K较小时（如K≤10），优先队列法更易实现

3. 注意事项：

   • 始终检查输入链表数组为空的情况
   • 处理链表节点时注意断链操作

---

附录：LeetCode测试用例验证
本文所述方法均已通过LeetCode以下测试场景：

• 空链表输入
• 单链表输入
• 超长链表（10^4级别节点）
• 大规模链表数（K=10^4）

掌握这些核心方法，将能从容应对绝大多数链表合并相关的算法挑战！