给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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的PriorityQueue数据结构(PriorityQueue实质就是
小根堆
),你add()一个数,PriorityQueue会自动排序,poll()一个数,会返回堆中的最小值。大体流程:
- 遍历lists每个元素(每个元素就是一个链表),将每个链表的头结点加入到小根堆中,然后首次poll()出来的就是lists所有链表中头最小的,拿它当做新链表的头。
- 然后判断该链表还有没有后继结点,如果有再加入到小根堆
- 再poll()出来一个,拼到新链表的后面,如果poll()的节点还有后继节点再加入,什么时候小根堆为空了
返回新链表
public class Problem_0023_MergeKSortedLists {
public static class ListNode {
public int val;
public ListNode next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) {
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>((a ,b) -> a.val - b.val);
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();
// pre负责拼接新链表
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;
}
}