合并K个升序链表 题目描述 给定一个链表数组，每个链表都已经按升序排列。你需要将所有链表合并到一个新的升序链表中，并返回这个新链表。 例如： 输入：lists = [ [ 1,4,5],[ 1,3,4],[ 2,6] ] 输出：[ 1,1,2,3,4,4,5,6 ] 解释：将所有链表合并后得到一个新的有序链表。 解题过程 问题分析 合并多个有序链表时，最直接的方法是两两合并。例如，先合并前两个链表，再将结果与第三个链表合并，依此类推。但这种方法效率较低，因为每个节点可能需要多次比较。更高效的方法是使用分治或优先队列（最小堆）来减少比较次数。 关键思路 最小堆优化 ：每次从所有链表的当前头节点中选出最小的节点，加入结果链表。利用最小堆（优先队列）可以快速获取最小值。 分治法 ：将k个链表两两分组合并，重复这一过程直到只剩一个链表。这种方法类似归并排序的分治策略。 最小堆解法步骤 步骤1 ：创建一个最小堆（优先队列），用于存储所有链表的当前头节点。堆按节点值排序。 步骤2 ：将所有链表的头节点加入堆中（如果头节点非空）。 步骤3 ：循环从堆中弹出最小节点，将其加入结果链表。如果该节点有下一个节点，将下一个节点加入堆。 步骤4 ：当堆为空时，所有节点已处理完毕，返回结果链表的头节点。 示例演示 （以输入[ [ 1,4,5],[ 1,3,4],[ 2,6] ]为例）： 初始堆：[ 1(链表1), 1(链表2), 2(链表3) ]。 弹出1(链表1)，加入结果，将其下一个节点4加入堆 → 堆：[ 1(链表2), 2(链表3), 4(链表1) ]。 弹出1(链表2)，加入结果，将3加入堆 → 堆：[ 2(链表3), 3(链表2), 4(链表1) ]。 重复过程直至堆空，最终得到有序链表。 复杂度分析 时间复杂度：O(N log k)，其中N为节点总数，k为链表数。每个节点进出堆一次，堆操作耗时O(log k)。 空间复杂度：O(k)，堆的大小最多为k。 分治解法补充 将k个链表递归分成两半，分别合并后再合并两个结果。 时间复杂度同样为O(N log k)，但无需额外堆结构，递归栈空间为O(log k)。