```
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
if (n == 0)
return NULL;
if (n == 1)
return lists[0];
return recursionMerge(lists, 0, n-1);
}
ListNode* recursionMerge(vector<ListNode*>& lists, int start, int end)
{
if (start == end)
return lists[start];
int mid = start + (end - start) / 2;
ListNode *l1 = recursionMerge(lists, start, mid);
ListNode *l2 = recursionMerge(lists, mid+1, end);
ListNode head(0);
ListNode *cur = &head;
while (l1 && l2)
{
if (l1->val <= l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1 != NULL)
cur->next = l1;
else
cur->next = l2;
return head.next;
}
};
```