合并K个升序链表

题目描述
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，并返回合并后的链表。

解题过程

1. 问题分析

   • 输入是K个已经排序的链表，每个链表可能长度不同。
   • 目标是合并所有链表，保持整体升序。
   • 直接两两合并（如先合并前两个，再合并结果与第三个）效率较低，时间复杂度为O(K² * 平均链表长度)。

2. 关键思路

   • 使用最小堆（优先队列）优化：始终维护当前所有链表头节点中的最小值。
   • 步骤：
     1. 将K个链表的头节点加入最小堆。
     2. 每次从堆中取出最小节点，将其加入结果链表。
     3. 若该节点有下一个节点，将下一个节点加入堆。
     4. 重复直到堆为空。

3. 详细步骤

   • 步骤1：创建虚拟头节点dummy和指针cur指向它，用于构建结果链表。
   • 步骤2：初始化最小堆，将每个链表的头节点入堆（需处理空链表情况）。
   • 步骤3：循环直到堆为空：
     • 弹出堆顶节点（当前最小值），将其链接到cur后。
     • 移动cur到新节点。
     • 若该节点有下一个节点，将下一个节点入堆。
   • 步骤4：返回dummy.next作为合并后的头节点。

4. 复杂度分析

   • 时间复杂度：O(N log K)，其中N为总节点数，K为链表数。每个节点入堆一次，堆操作耗时log K。
   • 空间复杂度：O(K)，堆中最多存K个节点。

5. 边界情况

   • 输入为空数组：直接返回null。
   • 某个链表为空：跳过该链表即可。