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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <cstddef>
#include <queue>
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty())  return NULL;
        if (lists.front() == lists.back())   return lists.back();
        ListNode* first = lists.back();
        lists.pop_back();
        ListNode* second =  lists.back();
        lists.pop_back();
        queue<ListNode*> merge;
        while(first !=NULL && second != NULL){
            if (first->val > second->val){
                merge.push(second);
                second = second->next;
            }else{
                merge.push(first);
                first = first->next;
            }
        }
        while(first != NULL){
            merge.push(first);
            first = first->next;
        }
        while(second != NULL){
            merge.push(second);
            second = second->next;
        }
        ListNode* start = merge.front();
        ListNode* index = start;
        merge.pop();
        while(!merge.empty()){
            index->next = merge.front();
            index = index->next;
            merge.pop();
        }
        index->next = NULL;
        lists.push_back(start);
        return mergeKLists(lists);
    }
};
/*
1)当lists中没有列表时，直接返还NULL（我一开始没考虑这个，w了一个点）
2)当lists中只有一个列表时，这个列表就是我们需要的列表
3)当lists中有多个列表时，取出两个合并并放回lists，重复2）3）
*/