Priority queue short solution cpp


  • 1
    S
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    class Solution {
        struct compareListNode{
            bool operator()(const ListNode* lhs,const ListNode* rhs){
                return lhs->val > rhs->val;
            }
        };
        
        
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode prehead(0),*cur=NULL,*min=NULL;
            priority_queue<ListNode*,vector<ListNode*>, compareListNode> pq;
            prehead.next=NULL;cur=&prehead; 
            for(int i=0;i<lists.size();++i){
                if(lists[i]!=NULL) 
                    pq.push(lists[i]);
                }
                
            while(!pq.empty())
            {
                min=pq.top();pq.pop();
                cur->next=min;cur=cur->next;
                if(min->next) pq.push(min->next);
            }
            //cur->next=NULL;
                    
            return prehead.next;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.