使用归并
/**
* 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;
if(lists.length==1)return lists[0];
return merge(lists,0,lists.length-1);
}
public ListNode merge(ListNode[] lists,int low,int high){
if(high==low){
return lists[high];
}
if(high-low==1)
return merge2Lists(lists[low],lists[high]);
if(high<low)
return null;
return merge2Lists(merge(lists,low,(low+high)/2),merge(lists,(low+high)/2+1,high));
}
public ListNode merge2Lists(ListNode x,ListNode y){
if(x==null)return y;
if(y==null)return x;
ListNode cur = null,head = null;
ListNode p = x, q = y;
if(p.val<=q.val){
cur = p;
p = p.next;
}else{
cur = q;
q = q.next;
}
head = cur;
while(p!=null&&q!=null){
if(p.val<=q.val){
cur.next = p;
p = p.next;
}else{
cur.next = q;
q = q.next;
}
cur = cur.next;
}
if(p==null)cur.next=q;
if(q==null)cur.next=p;
return head;
}
}
