Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
本题目我第一个想到了用小顶堆来做，不是很难，直接上代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null||lists.length==0) return null;
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
public int compare(ListNode a,ListNode b){
return a.val-b.val;
}
});
for(ListNode l:lists){
if(l!=null) q.offer(l);
}
ListNode node = new ListNode(0);
ListNode dummy = node;
while(!q.isEmpty()){
ListNode next = q.poll();
node.next = next;
node = node.next;
next = next.next;
if(next!=null) q.offer(next);
}
return dummy.next;
}
}
后来看了标签，发现还可以用分治的方法来做（也就是递归）,代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
if(lists.length==1) return lists[0];
if(lists.length==2) return mergeTwoLists(lists[0],lists[1]);
return mergeTwoLists(mergeKLists(Arrays.copyOfRange(lists,0,lists.length/2)),mergeKLists(Arrays.copyOfRange(lists,lists.length/2,lists.length)));
}
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
ListNode node = new ListNode(0);
ListNode dummy =node;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
ListNode next = l1;
node.next = next;
node = node.next;
l1 = l1.next;
}else{
ListNode next = l2;
node.next = next;
node = node.next;
l2 = l2.next;
}
}
if(l1!=null){
node.next = l1;
}
if(l2!=null){
node.next = l2;
}
return dummy.next;
}
}