思路：

• 利用归并排序的原理，k个已排序链表可以分成前k/2个已排序链表和后k/2个已排序链表，这两部分链表可以再继续递归地进行划分；

• 递归到每组只剩一个链表时，再两两合并。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;

        return mergeLists(lists, 0, lists.size());
    }

    //使用归并排序分割链表集
    ListNode* mergeLists(vector<ListNode*>& lists, int start, int end)
    {
        if (start + 1 == end)
        {
            return lists[start];
        }

        int mid = (start + end) >> 1;
        ListNode* head1 = mergeLists(lists, start, mid);    //前`k/2`个已排序链表
        ListNode* head2 = mergeLists(lists, mid, end);      //后`k/2`个已排序链表

        return merge(head1, head2);
    }

    //合并两个已排序链表（模板）
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        if (head1 == nullptr || head2 == nullptr)
        {
            return head1 == nullptr ? head2 : head1;
        }

        ListNode *dummy = new ListNode(0), *cur = dummy;

        while (head1 != nullptr && head2 != nullptr)
        {
            if (head1->val < head2->val)
            {
                cur = cur->next = head1;
                head1 = head1->next;
            }
            else
            {
                cur = cur->next = head2;
                head2 = head2->next;
            }
        }

        if (head1 != nullptr) cur->next = head1;
        if (head2 != nullptr) cur->next = head2;

        return dummy->next;
    }
};