/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(vector<ListNode*>&lists, int start, int end){
        if(start==end)return lists[start];
        int mid=(start+end)/2;
        ListNode*p1=merge(lists, start, mid);
        ListNode*p2=merge(lists, mid+1, end);
        ListNode*head=NULL, *p=NULL;
        while(p1&&p2){
            if(p1->val<p2->val){
                if(p)p->next=p1;
                p=p1;
                p1=p1->next;
            }
            else{
                if(p)p->next=p2;
                p=p2;
                p2=p2->next;
            }
            
            if(head==NULL)head=p;
        }
        if(p1){
            if(p)p->next=p1;
            else{p=p1;head=p;}
        }
        if(p2){
            if(p)p->next=p2;
            else{p=p2;head=p;}
        }
        return head;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
		int size=lists.size();
		if(size==0) return NULL;
		if(size==1) return lists[0];
		return merge(lists, 0, size-1);
    }
};