- 难度：
困难 - 本题涉及算法：
优先队列 - 思路：
优先队列 - 类似题型:
23. 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
方法一 优先队列
解题思路
- 通过题目和示例，可清楚的了解到，其实就是 合并元素，并 排序
- 第一步通队列保存链表元素
- 对队列排序
- 通过优先队列，可完成上述两个步骤
Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> Integer.compare(i2, i1));时间复杂度：$O(n*log(k))$，n 是所有链表中元素的总和，k 是链表个数
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> Integer.compare(i2, i1));
// 合并链表元素到队列
for(ListNode node:lists){
while (node != null){
queue.offer(node.val);
node = node.next;
}
}
// 把队列中元素添加到了新的链表
ListNode ans = null;
while (!queue.isEmpty()){
ListNode curr = new ListNode(queue.poll()); // 每次拿出最大元素，并删除
curr.next = ans;
ans = curr;
}
return ans;
}
}
PREVIOUS26. 删除排序数组中的重复项
NEXT21. 合并两个有序链表