/**
* 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.length==0)
return null;
Queue<ListNode> pq=new PriorityQueue(lists.length,new Comparator<ListNode>()
{
@Override
public int compare(ListNode o1,ListNode o2)
{
return o1.val-o2.val;
}
});
ListNode root=new ListNode(0);
for(int i=0;i<lists.length;i++)
if(lists[i]!=null)
pq.add(lists[i]);
ListNode p=root;
while(!pq.isEmpty())
{
ListNode q=pq.remove();
p.next=q;
p=p.next;
if(q.next!=null)
pq.add(q.next);
}
return root.next;
}
}
//分治法
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0)
return null;
return mergeLists(lists,0,lists.length-1);
}
public ListNode mergeLists(ListNode[] lists,int l,int r)
{
if(l==r)
return lists[l];
int mid=l+(r-l)/2;
ListNode l1=mergeLists(lists,l,mid);
ListNode l2=mergeLists(lists,mid+1,r);
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;
}
else
{
l2.next=merge(l1,l2.next);
return l2;
}
}
}