# A solution to merge k sorted linked list beat all solutions

• class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
int sz = lists.size();
if (sz){
return BinaryMergeList(lists, 0, sz - 1);
}
}
private:
ListNode* copy(ListNode* node){
if (node)
return new ListNode(node->val);
else
return NULL;
}
ListNode* BinaryMergeList(vector<ListNode*>& lists, int start, int end){
if (start > end){
return NULL;
}
else if (start == end){
return lists[start];
}
else if (start == end - 1){
return mergeTwoList(lists[start], lists[end]);
}
else{
int middle = (start + end) >> 1;
return mergeTwoList(BinaryMergeList(lists,start,middle),BinaryMergeList(lists,middle+1,end));
}
}
ListNode* mergeTwoList(ListNode* first, ListNode* second){
if (!first && second){
}
else if (first && !second){
}
else if(first && second){
if (first->val <= second->val){
first = first->next;
}
else{
second = second->next;
}
while (first && second){
if (first->val <= second->val){
cur->next = first;
cur = first;
first = first->next;
}
else{
cur->next = second;
cur = second;
second = second->next;
}
}
if(first){
cur->next = first;
}
if(second){
cur->next = second;
}
}