• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode 合并K个升序链表 困难

开发技术 开发技术 5小时前 2次浏览

leetcode 合并K个升序链表 困难

 

 

其实和合并两个有序链表区别并不大,但如果遍历每个链表的头结点,复杂度就高了,即每连一个节点,需要遍历一次链表数组的当前头。

优化:用优先队列来解决这个问题

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个升序链表 困难
喜欢 (0)