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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty())
            return NULL;
        auto res = merge(lists);
        return res[0];
    }
// 具体思想：先将lists数组后面的两个链表进行合并，然后当lists数组中的元素只有一个时，返回lists数组
    vector<ListNode* > merge(vector<ListNode* >& lists) {
        if(lists.size() < 2)
            return lists;
        int n = lists.size();
        auto l1 = lists[n - 1], l2 = lists[n - 2];
        ListNode* head = new ListNode(-1);
        auto l = head;
        lists.pop_back();
        lists.pop_back();
        while(l1 && l2) {
            if(l1->val < l2->val) {
                auto q = new ListNode(l1->val);
                l->next = q;
                l1 = l1->next;
            }
            else {
                auto q = new ListNode(l2->val);
                l->next = q;
                l2 = l2->next;
            }
            l = l->next;
        }
        while(l1) {
            auto q = new ListNode(l1->val);
            l->next = q;
            l1 = l1->next;
            l = l->next;
        }
        while(l2) {
            auto q = new ListNode(l2->val);
            l->next = q;
            l2 = l2->next;
            l = l->next;
        }
        lists.push_back(head->next); // 将合并的链表存入队列
        merge(lists);
        return lists;
    }
};