C/C++教程

leetcode 合并 k 个升序链表 困难

本文主要是介绍leetcode 合并 k 个升序链表 困难,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

 

用优先队列维护 ListNode*,根据其 val 值做小顶堆,每一次都取小顶堆堆订连接上即可

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        for(auto &item : lists){
            if(item) pq.push(item);
        }
        ListNode *head = new ListNode, *temp = head;
        while(!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            temp -> next = top;
            top = top -> next;
            temp = temp -> next;
            if(top) pq.push(top);
        }
        auto ret = head -> next;
        delete head;
        return ret;
    }
    
    struct Compare {
        bool operator()(ListNode *l1, ListNode *l2) {
            return l1 -> val > l2->val;
        }
    };
};

 

这篇关于leetcode 合并 k 个升序链表 困难的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!