ListNode* mergeKLists(vector<ListNode*>& lists) {
int k = (int)lists.size();
if(k==0) return NULL;
if(k==1) return lists[0];
return doMerge(lists, 0, (int)lists.size()1);
}
ListNode* doMerge(vector<ListNode*>& lists, int left, int right) {
if(left==right) return lists[left];
else if(left+1==right) return merge2Lists(lists[left], lists[right]);
ListNode* l1 = doMerge(lists, left, (left+right)/2);
ListNode* l2 = doMerge(lists, (left+right)/2+1, right);
return merge2Lists(l1, l2);
}
ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
if(l1==l2) return l1;
if(!l1) return l2;
if(!l2) return l1;
if(l1>val>l2>val) return merge2Lists(l2, l1);
ListNode* newl2 = new ListNode(0); newl2>next = l2;
ListNode* p1 = l1;
while (p1>next && newl2>next) {
if (p1>next>val<newl2>next>val) {
p1 = p1>next;
} else {
ListNode* temp = p1>next;
p1>next = newl2>next;
newl2>next = newl2>next>next;
p1>next>next = temp;
p1 = p1>next;
}
}
if(!p1>next) p1>next = newl2>next;
delete newl2;
return l1;
}
C++ code O(NlogK) in time, O(1) in space, Divide_Conquer


I had the same idea with you! ^_^
ListNode *merge2Lists(ListNode *list1, ListNode *list2) { if(NULL == list1) return list2; if(NULL == list2) return list1; ListNode res(0); ListNode *curRes = &res, *cur1 = list1, *cur2=list2; while(cur1 != NULL && cur2 != NULL) { if(cur1>val < cur2>val) { curRes>next = cur1; cur1 = cur1>next; }else { curRes>next = cur2; cur2 = cur2>next; } curRes = curRes>next; } curRes>next = cur1 ? cur1 : cur2; return res.next; } ListNode *mergeKLists(ListNode *list[], int size){ if(0 == size) return NULL; if(1 == size) return list[0]; if(2 == size) { return merge2Lists(list[0], list[1]); } int mid = size>>1; ListNode *subList1 = mergeKLists(list, mid); ListNode *subList2 = mergeKLists(&list[mid], size  mid); return merge2Lists(subList1, subList2); } ListNode *mergeKLists(vector<ListNode *> &lists) { return mergeKLists(&lists[0], lists.size()); }

the time complexity of your algorithm is o(nklogk), absolutely.
assume the average length of lists is n, there are k lists.
firstly, merge every two list need nk/2; in the next round, the length of list becomes 2n, the number of lists becomes k/2, so the complexity is still nk/2. Keep such rounds until k == 1, that would be log(k) rounds. so the total complexity is nklog(k)