一、題目大意
標簽: 堆疊和佇列
https://leetcode.cn/problems/merge-k-sorted-lists
給你一個鏈表陣列，每個鏈表都已經按升序排列，
請你將所有鏈表合并到一個升序鏈表中，回傳合并后的鏈表，
示例 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
二、解題思路
這里需要將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 疫情常態化了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501587.html
標籤：其他
下一篇：H3C HCL與WSL2共存