LeetCode 23：合并 K 个升序链表

LeetCode 23：合并 K 个升序链表

问题本质：多有序链表的归并

给定 K 个升序链表，需合并为一个全局升序链表，返回其头节点。核心是高效处理多链表的有序合并，避免暴力法的高复杂度。

核心思路：两种高效解法

1. 优先队列（最小堆）

• 核心逻辑：维护当前所有链表头节点的最小值，每次取最小节点加入结果，再将该节点的下一个节点（若存在）加入堆，循环至所有节点处理完毕。
• 优势：利用堆的排序特性，保证每次取最小值的时间为 O(logK)，整体高效。

2. 分治合并

• 核心逻辑：类似归并排序，将 K 个链表递归拆分为两两一组，合并后再递归合并结果，最终得到全局有序链表。
• 优势：递归结构清晰，空间复杂度更优（递归栈深度为 O(logK)）。

方法一：优先队列（最小堆）详解

步骤 1：处理边界情况

• 若 lists 为空或所有链表为空，直接返回 null。

步骤 2：初始化优先队列

• 使用 PriorityQueue 实现最小堆，比较器按节点值从小到大排序。
• 遍历 lists，将非空链表的头节点加入堆（过滤空链表，避免空指针）。

步骤 3：构建结果链表

• 创建虚拟头节点（dummy），简化链表拼接（无需处理头节点为空的边界）。
• 循环处理堆：
  1. 取出堆顶元素（当前最小节点），接入结果链表。
  2. 若该节点有下一个节点，将其加入堆（维持堆的动态更新）。

步骤 4：返回结果

• 虚拟头节点的 next 即为合并后链表的头节点。

方法二：分治合并详解

步骤 1：递归终止条件

• 若链表数组为空，返回 null。
• 若只剩一个链表，直接返回该链表（递归基例）。

步骤 2：递归拆分

• 将链表数组分为左右两半，递归合并左右部分，得到两个局部合并后的链表 l1 和 l2。

步骤 3：合并两个有序链表

• 实现辅助函数 mergeTwoLists，用双指针法合并两个有序链表：
  • 比较两链表当前节点值，将较小值接入结果链表，指针后移。
  • 处理剩余未遍历的节点（直接拼接）。

步骤 4：递归合并结果

• 合并 l1 和 l2，返回最终结果。

完整代码实现

方法一：优先队列（最小堆）

/**
 * 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 mergeKLists(ListNode[] lists) {
        // 边界处理：空输入
        if (lists == null || lists.length == 0) return null;
        
        // 初始化最小堆，按节点值排序
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // 将非空链表的头节点加入堆
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }
        
        // 虚拟头节点，简化拼接
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        
        // 处理堆中的节点
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll(); // 取出当前最小节点
            curr.next = minNode;              // 接入结果链表
            curr = curr.next;                 // 指针后移
            
            // 将下一个节点加入堆（若存在）
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }
        
        return dummy.next;
    }
}

方法二：分治合并

/**
 * 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 mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    
    // 递归合并区间 [left, right] 的链表
    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);
    }
    
    // 合并两个有序链表（双指针法）
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        // 拼接剩余节点（其中一个链表已遍历完）
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度分析

优先队列法

• 时间复杂度：O(N logK)，其中 N 是所有链表的总节点数，K 是链表个数。每个节点入堆、出堆各一次，堆操作时间为 O(logK)。
• 空间复杂度：O(K)，堆中最多存储 K 个节点（初始头节点数）。

分治合并法

• 时间复杂度：O(N logK)，每层合并的总节点数为 N，共 logK 层（递归深度）。
• 空间复杂度：O(logK)，递归栈的深度为 logK（分治层数），额外空间为 O(1)（双指针合并的虚拟节点）。

示例验证

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]

• 优先队列法：堆初始包含 1、1、2，每次取最小节点，依次拼接，最终得到 1→1→2→3→4→4→5→6。
• 分治合并法：递归拆分合并，最终结果一致。

总结

两种方法均能高效解决问题，核心是利用排序或分治降低复杂度：

• 优先队列：直观高效，适合处理动态更新的最小节点选取。
• 分治合并：递归简洁，空间更优，体现“分而治之”的算法思想。

根据场景选择：若需快速实现，优先队列更直接；若追求空间优化，分治合并更优。两者时间复杂度一致，均为 O(N logK)，是解决多有序链表合并的经典方案。