23. Merge k Sorted Lists

题目：

解答：

这道题有两种解法：

基础解法： 遍历每个链表头，取出最小值，并保持将空链表从选取集里面剔除。
堆排序解法： 通过设置一个链表最小堆，维护一个拥有最小值链表头的节点在堆顶。这里注意使用make_heap和c++11新功能的emplace的差别。如果时刻使用make_heap维护堆的有效性，会运行效率缓慢，如果通过emplace对已经符合规则的堆操作，效率会快很多，从 $n\log(n) \to \log(n)$

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class comp{
    public:
    bool operator()(const ListNode* A, const ListNode* B)const {
        return A->val > B->val;
    }  
};
class Solution {
public:
    //解法一，运行72ms
    ListNode* mergeKListsV1(vector<ListNode*>& lists) {
        vector<ListNode*> L;
        for(int i = 0;i < lists.size();++i){
            if(lists[i] != NULL)    L.push_back(lists[i]);
        }
        ListNode* head = new ListNode(-1), *p = head;
        int len = L.size();
        while(len > 0){
            int maxnum = INT_MAX, index = -1;
            for(int i = 0;i < len; ++i){
                if(L[i]->val < maxnum){
                    maxnum = L[i]->val;
                    index = i;
                }
            }
            p->next = L[index];
            p = p->next;
            L[index] = L[index]->next;
            if(L[index] == NULL){
                --len;
                swap(L[index], L[len]);
            }
        }
        p = head->next;
        delete head, head = NULL;
        return p;
    }
    // 解法二，运行效率28ms，这里注意，如果将最后delete操作去掉，是可以提高运行效率，但是会造成
    // 内存泄漏，是不可取的（leetcode上最佳答案是这样省略掉，加速时间）
    ListNode* mergeKListsV2(vector<ListNode*>& lists) {
        if(lists.empty())   return NULL;
        int len = lists.size();
        priority_queue<ListNode*, vector<ListNode*>, comp> L;
        for(const auto& node: lists){
            if(node != NULL)    L.emplace(node);
        }
        ListNode* head = new ListNode(-1), *p = head;
        while(!L.empty()){
            ListNode* tmp = L.top();
            L.pop();
            p->next = tmp;
            p = p->next;
            tmp = tmp->next;
            if(tmp != NULL)
                L.emplace(tmp);
        }
        p = head->next;
        delete head, head = NULL;
        return p;
    }
};
// 解法三，使用make_heap代替emplace方法，速度为800ms，可以看出，效率是很低的。
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    static int comp(ListNode* A, ListNode* B){
        return A->val > B->val;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> L;
        for(int i = 0;i < lists.size();++i){
            if(lists[i] != NULL)    L.push_back(lists[i]);
        }
        if(lists.size() == 0)   return NULL;
        make_heap(L.begin(), L.end(), comp);
        ListNode* head = new ListNode(-1), *p = head;
        while(L.size() > 0){
            p->next = L.front();
            p = p->next;
            L.front() = L.front()->next;
            if(L.front() == NULL)
                pop_heap(L.begin(), L.end()), L.pop_back();
            make_heap(L.begin(), L.end(), comp);
        }
        p = head->next;
        delete(head), head = NULL;
        return p;
    }
};

更新会同步在我的网站更新(https://zergzerg.cn/notes/webnotes/leetcode/index.html)

23. Merge k Sorted Lists

相关推荐