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;
        }
    };
};

 

上一篇:剑指 Offer II 059. 数据流的第 K 大数值


下一篇:文献阅读报告 - 3DOF Pedestrian Trajectory Prediction