Merge Using Queue


  • 0
    S

    struct Node{
    ListNode *head;
    bool operator < (const struct Node &t) const {
    return (head->val > t.head->val);
    }
    };
    priority_queue<Node,vector<Node>> min_heap;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        ListNode *dummy = new ListNode(0);
        ListNode *new_list = dummy;
        /* Use Min heap */ 
        // Add an element from each List */ 
        for (auto l : lists){
              if(l != NULL){
                min_heap.emplace(Node{l});
              }
        }
        while(!min_heap.empty()){
            ListNode *t = min_heap.top().head;
            new_list->next = new ListNode(t->val);
            new_list = new_list->next;
            min_heap.pop();
            if(t->next != NULL){
               min_heap.emplace(Node{t->next});
            }
        }
        
        return dummy->next;
    }

Log in to reply
 

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