合并K个有序链表

力扣题目链接

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

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

示例 1：

输入：lists = [[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

示例 2：

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

示例 3：

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

提示：

• 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

解题思路：最小堆优先队列

本题其实就是合并链表问题，将链表按照升序的顺序合并成一个大的链表

合并链表其实挺好实现，本题的难点就在于合并链表时，如何得到每个链表的最小结点，并将最小结点结到结果链表中

这里我们就需要用到 优先队列(最小堆) 这种数据结构，堆的本质是完全二叉树，可以通过数组方式顺序存储；每当堆发生变换时，需要通过节点的上浮和下沉操作，来保证堆的节点之前的严格大小关系。因为最小堆有个特点，子类数字总是大于父类数字。

所以我们可以用最小堆排序来实现，将所有链表放进最小堆里，排序，每次只需要取出堆内最小的元素，将元素放到结果链表中，循环取元素，直到堆内为空

解题代码：（JAVA实现）

class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		if(lists==null || lists.length==0) {
			return null;
		}
		//创建一个堆，并设置元素的排序方式
		PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
			public int compare(ListNode o1, ListNode o2) {
				return (o1.val - o2.val);
			}
		});
		//遍历链表数组，然后将每个链表的每个节点都放入堆中
		for(int i=0;i<lists.length;i++) {
			while(lists[i] != null) {
				queue.add(lists[i]);
				lists[i] = lists[i].next;
			}
		}
		ListNode dummy = new ListNode(-1);
		ListNode head = dummy;
		//从堆中不断取出元素，并将取出的元素串联起来
		while( !queue.isEmpty() ) {
			dummy.next = queue.poll();
			dummy = dummy.next;
		}
		dummy.next = null;
		return head.next;
	}
}

复杂度分析：

• 时间复杂度：O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数
• 空间复杂度：O(1)

提交结果