LeetCode23 合并k个升序链表
题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
方法
分治法
把数组用二分法，先讲数组分成两两结合，然后层层两两合并
- 时间复杂度： O(kn×logk)，k为数组个数
- 空间复杂度： O(logk)，二分法
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists,0,lists.length-1);
}
private ListNode merge(ListNode[] lists,int l,int r){
if(l==r){
return lists[l];
}
if(l>r){
return null;
}
int mid = (l+r)/2;
return mergeTwoList(merge(lists,l,mid),merge(lists,mid+1,r));
}
private ListNode mergeTwoList(ListNode node1,ListNode node2){
ListNode head = new ListNode(),node = head;
while(node1!=null&&node2!=null){
if(node1.val优先队列法
将数组的节点存入优先队列，优先队列会根据节点的值排序，然后取过值的节点往下找next，并继续存入队列中排序
- 时间复杂度： O(kn×logk)
- 空间复杂度： O(k)，优先队列节点个数
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue priorityQueue = new PriorityQueue(new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
for(ListNode node:lists){
if(node!=null){
priorityQueue.offer(node);
}
}
ListNode head = new ListNode();
ListNode tail = head;
while(!priorityQueue.isEmpty()){
ListNode node = priorityQueue.poll();
tail.next = node;
tail = tail.next;
if(node.next!=null){
priorityQueue.offer(node.next);
}
}
return head.next;
}
}