题解 | #合并k个已排序的链表#

采用归并排序的套路，递归将lists一直从中间拆分，直到不能再拆，在递归函数返回时，将拆分的两段list1[a:b]和list2[c:d]进行合并，合并结果保存在list1[a]中，这样，最终合并的结果在lists[0]中。

class Solution {
public:
    ListNode * merge2lists(ListNode *list1, ListNode *list2)
    {
        ListNode node(0);
        ListNode *p = &node;

        while (list1 && list2)
        {
            if (list1->val <= list2->val)
            {
                p->next = list1;
                p = p->next;
                list1 = list1->next;
            }
            else
            {
                p->next = list2;
                p = p->next;
                list2 = list2->next;
            }
        }

        if (list1)
        {
            p->next = list1;
        }

        if (list2)
        {
            p->next = list2;
        }

        return node.next;
    }
    
    void merge(vector<ListNode *> &lists, int beg, int end)
    {
        if (beg >= end)
        {
            return;
        }
        
        int m = (beg + end) / 2;
        merge(lists, beg, m);
        merge(lists, m + 1, end);

        ListNode *list1 = lists[beg];
        ListNode *list2 = lists[m + 1];
        lists[beg] = merge2lists(list1, list2);
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty())
            return NULL;
        
        merge(lists, 0, lists.size() - 1);

        return lists[0];
    }
};