🔗 合并 K 个升序链表

题目来源：23. 合并 K 个升序链表 – 力扣（LeetCode）

📌 题目描述

给你一个链表数组 lists，每个链表中的节点已按升序排列。

请将所有链表合并成一个升序链表并返回其头节点。

✅ 示例解析

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：合并三个有序链表 → 最终全局有序。

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

⚠️ 提示

• k == lists.length
• 0 <= k <= 10⁴
• 每个链表长度 <= 500
• 节点值范围：[-10⁴, 10⁴]
• 所有链表已升序排列
• 总节点数 <= 10⁴

💡 解法：分治归并 —— O(N log K) 时间，O(log K) 空间

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

    private ListNode split(ListNode[] lists, int i, int j) {
        if (i == j) return lists[i];
        int m = (i + j) >>> 1;
        ListNode left = split(lists, i, m);
        ListNode right = split(lists, m + 1, j);
        return merge(left, right);
    }

    private ListNode merge(ListNode a, ListNode b) {
        if (a == null) return b;
        if (b == null) return a;
        ListNode dummy = new ListNode(0), p = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                p.next = a;
                a = a.next;
            } else {
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }
        p.next = a != null ? a : b;
        return dummy.next;
    }
}

📊 复杂度分析

• 时间复杂度：O(N log K)
  • N：所有链表节点总数
  • K：链表个数
  • 每层合并总耗时 O(N)，共 log K 层
• 空间复杂度：O(log K)
  • 递归调用栈深度（分治树高度）

🧩 解题思路

核心思想：分治 + 两两归并

1. 递归分治：
   • 将 K 个链表不断二分，直到只剩 1 个链表（直接返回）
   • 然后两两向上合并
2. 合并有序链表：
   • 复用经典“合并两个有序链表”逻辑
   • 使用哨兵节点简化头节点处理
3. 边界处理：
   • 空数组 → 返回 null
   • 单链表 → 直接返回
   • 空链表 → merge 中自动跳过