Leetcode-23-合并K个升序链表(Merge k Sorted Lists)
23. 合并K个升序链表
难度困难1281收藏分享切换为英文接收动态反馈
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4-
lists[i]按 升序 排列 -
lists[i].length的总和不超过10^4
- Merge k Sorted Lists
Hard
7059355Add to ListShare
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4-
lists[i]is sorted in ascending order. - The sum of
lists[i].lengthwon't exceed10^4.
小跟堆解题，放入每个有序链表的表头，小跟堆poll出最小的的Node，串联在输出的Node上。
public static class ListNodeComparator implements Comparator<ListNode> {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
}
public static ListNode mergeKLists(ListNode[] lists) {
if (lists == null) {
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
heap.add(lists[i]);
}
}
if (heap.isEmpty()) {
return null;
}
ListNode head = heap.poll();
ListNode pre = head;
if (pre.next != null) {
heap.add(pre.next);
}
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
pre.next = cur;
pre = cur;
if (cur.next != null) {
heap.add(cur.next);
}
}
return head;
}
image-20210501200956264
