class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        ListNode res=lists[0];        
        for(int i=1; i<lists.length; i++)
            res=merge(res, lists[i]);
        return res;
    }
    public ListNode merge(ListNode res, ListNode list){
        ListNode l1=new ListNode(0);
        ListNode head=l1;
        while(res!=null && list!=null){
            if(res.val<list.val){
                l1.next=res;
                res=res.next;
            }else{
                l1.next=list;
                list=list.next;
            }
            l1=l1.next;
        }
        while(res!=null){
            l1.next=res;
            res=res.next;
            l1=l1.next;
        }
        while(list!=null){
            l1.next=list;
            list=list.next;
            l1=l1.next;
        }
        return head.next;
    }
}