一、题目粗心
标签: 栈和队列
https://leetcode.cn/problems/…
给你一个链表数组,每个链表都曾经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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 <= listsi <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
二、解题思路
这里须要将 k 个排序链表交融成一个排序链表,多个输出一个输入,相似于漏斗,因而能够利用最小堆的概念。
取每个 Linked List 的最小节点放入一个 heap 中,排成最小堆,而后取出堆顶最小的元素放入合并的 List 中,而后将该节点在其对应的 List 中的下一个节点插入到 heap 中,循环下面步骤。
三、解题办法
3.1 Java 实现
public class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
for (ListNode node : lists) {if (node != null) {pq.add(node);
}
}
ListNode ret = null;
ListNode cur = null;
while (!pq.isEmpty()) {ListNode node = pq.poll();
if (ret == null) {
cur = node;
ret = cur;
} else {
cur.next = node;
cur = cur.next;
}
if (node.next != null) {pq.add(node.next);
}
}
return ret;
}
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {this.val = val;}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
四、总结小记
- 2022/8/11 疫情常态化了