合并 k 个升序链表

题解思路

本题要求将多个已排序的链表合并成一个升序的链表。每个链表中的元素都已经排好序，我们需要利用这些已排序链表的信息将其合并为一个新的有序链表。

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

最小堆是一种数据结构，它支持在对元素进行插入和删除时，始终保持堆顶元素为最小值。我们可以利用最小堆来实现这个问题。

Leetcode 34.合并K个升序链表-原题链接

题目内容

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表

输入描述

第一行为一个整数$k$， 接下来的$k$行，每行若干个整数，以空格隔开，表示一个链表节点的值。

输出描述

输出共一行，包含排序后链表节点的值，用空格隔开。

样例1

输入

3
1 4 5
1 3 4
2 6

输出

1 1 2 3 4 4 5 6

说明

[ $1->4->5$, $1->3->4$, $2->6$ ] 将它们合并到一个有序链表中得到。 $1->1->2->3->4->4->5->6$

提示

• $k == lists.length$
• $0 <= k <= 10^4$
• $0 <= lists[i].length <= 500$
• $-10^4 <= lists[i][j] <= 10^4$
• $lists[i]$ 按升序 排列
• $lists[i].length$ 的总和不超过 $10^4$