Leetcode-023-Merge k sorted lists

这题是一道可以偷懒的题，把所有元素都读取一遍存起来，然后排序，再把排序后的值存到一个链表里就ok了……感觉运行效率还挺高的。代码如下：

/**
 * 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;
        vector<int> num;
        ListNode *temp;
        for(int i=0;i<lists.size();i++)
        {
            temp=lists[i];
            while(temp)
            {
                num.push_back(temp->val);
                temp=temp->next;
            }
        }
        if(num.empty())
            return NULL;
        sort(num.begin(),num.end());
        temp=new ListNode(num[0]);
        ListNode *ans=temp;
        for(int i=1;i<num.size();i++)
        {
            temp->next=new ListNode(num[i]);
            temp=temp->next;
        }
        return ans;
    }
};

时间复杂度还可以，空间复杂度略差，毕竟我开了一个数组来存放读取的元素。Discuss区看到一个用优先队列的方法，空间占用较少。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct compare {
    bool operator()(const ListNode* l, const ListNode* r) {
        return l->val > r->val;
    }
};
ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
    priority_queue<ListNode *, vector<ListNode *>, compare> q;
    for(auto l : lists) {
        if(l)  q.push(l);
    }
    if(q.empty())  return NULL;

    ListNode* result = q.top();
    q.pop();
    if(result->next) q.push(result->next);
    ListNode* tail = result;            
    while(!q.empty()) {
        tail->next = q.top();
        q.pop();
        tail = tail->next;
        if(tail->next) q.push(tail->next);
    }
    return result;
    }
};