这是一道直接暴力求解也可以通过的题目，题本身不难，但却是一道值得一练的题目，从两两合并的暴力求解，到分治和优化队列，以及其中每一种解法的复杂度分析，将这些捋清楚一遍还是大有裨益。我这里用了分治的方式解决，代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode head, *ptr_a = a, *ptr_b = b, *ptr_result = &head;
while (ptr_a && ptr_b) {
if (ptr_a->val < ptr_b -> val) {
ptr_result -> next = ptr_a;
ptr_result = ptr_a;
ptr_a = ptr_a -> next;
} else {
ptr_result -> next = ptr_b;
ptr_result = ptr_b;
ptr_b = ptr_b -> next;
}
}
if (!ptr_a&&ptr_b) {
ptr_result -> next = ptr_b;
} else if (ptr_a && !ptr_b) {
ptr_result -> next = ptr_a;
}
return head.next;
}
ListNode* mergeHelper(vector<ListNode*>& lists, int begin, int end) {
int middle = (end - begin) / 2 + begin;
if (begin == end)
return lists[begin];
else if (end - begin == 1)
return mergeTwoLists(lists[begin], lists[end]);
return mergeTwoLists(mergeHelper(lists, begin, middle), mergeHelper(lists, middle + 1, end));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0)
return nullptr;
return mergeHelper(lists, 0, lists.size() - 1);
}
};
