23. Merge k Sorted Lists

使用归并

/**
 * 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;
    }
}