合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
方法1：分治
time:O(nlogk) where k is the number of linked list
space:O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0)return null;
return sort(lists,0,lists.length - 1);
}
public ListNode sort(ListNode[] lists,int lo,int hi){
if(lo >= hi) return lists[lo];//奇数个的时候，两两合并会多出一个，此语句用于返回该list,在下一次进行合并
int mid = (hi - lo) / 2 + lo;
ListNode l1 = sort(lists,lo,mid);
ListNode l2 = sort(lists,mid+1,hi);
return merge(l1,l2);
}
public ListNode merge(ListNode l1,ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = merge(l1.next,l2);
return l1;
}
l2.next = merge(l1,l2.next);
return l2;
}
}
方法2：优先级队列
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0)return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a,b)->a.val-b.val);
ListNode dummy = new ListNode(0);
ListNode cur = dummy; for(ListNode list : lists){
if(list != null){
queue.add(list);
}
}
while(!queue.isEmpty()){
cur.next = queue.poll();
cur = cur.next;
if(cur.next != null){
queue.add(cur.next);
}
}
return dummy.next;
} }
2019-04-19 10:07:41