Simple C++ solution using heaps O(n*logk)


  • -1
    B

    It's pretty straightforward. Maintain a heap of size K, everytime we pop off the min element, then push it's next element on the heap if it's not null. Maintain a curr pointer so we can link all the nodes together, as well as a head pointer for the first pop.

    class Solution {
    public:
        struct NodeCmp {
            bool operator()(ListNode *a, ListNode *b) {
                return a->val > b->val;
            }
        };
        
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            vector<ListNode*> heap;
            // make heap with the first element of each list
            for(int i = 0; i < lists.size(); ++i) {
                if (lists[i] != NULL) {
                    heap.push_back(lists[i]);
                }
            }
            make_heap(heap.begin(), heap.end(), NodeCmp());
            
            ListNode *head = NULL;
            ListNode *curr = NULL;
            while(!heap.empty()) {
                ListNode *min = heap.front();
                pop_heap(heap.begin(), heap.end(), NodeCmp());
                heap.pop_back();
                
                if(!head)
                    head = min;
                if(curr)
                    curr->next = min;
                curr = min;
                // add next element from list to heap if it's not null
                if(curr->next) {
                    heap.push_back(curr->next);
                    push_heap(heap.begin(), heap.end(), NodeCmp());
                }
            }
            return head;
        }
    };

  • 0

    you know lambda function can also be used:
    auto comp = [](pair<ListNode*, int> p1, pair<ListNode*, int> p2){
    return p1.first->val > p2.first->val;
    };


  • 0
    J
    This post is deleted!

  • 0
    S

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      class MyNode
      {
      public:
      ListNode
      pNode;
      int listId;
      };
      class Comparer
      {
      public:
      bool operator() (MyNode& p1, MyNode& p2)
      {
      return p1.pNode->val > p2.pNode->val;
      }
      };
      ListNode *mergeKLists(vector<ListNode *> &lists) {

       ListNode* pPrev = NULL;
       ListNode* pRet = NULL;
       
       priority_queue<MyNode, vector<MyNode>,Comparer> min_heap;
       
        for (int i =0; i< lists.size(); i++)
       {
           if (lists[i])
           {
               MyNode obj;
               obj.pNode = lists[i];
               obj.listId = i;
               min_heap.push(obj);
               lists[i] = lists[i]->next;
            }
       }
       
       while(min_heap.size())
       {
            
               MyNode Curr = min_heap.top();
               min_heap.pop();
               
               if (lists[Curr.listId])
               {
                   MyNode obj;
                   obj.pNode = lists[Curr.listId];
                   obj.listId = Curr.listId;   
                   min_heap.push(obj);
                   lists[Curr.listId] = lists[Curr.listId]->next;
               }
               
               if (pPrev)
                   pPrev->next = Curr.pNode;
               else
                   pPrev = pRet = Curr.pNode;
               
               pPrev = Curr.pNode;
           
       }
       if (pPrev)
           pPrev->next = NULL;
       
       return pRet;
      

      }
      };


Log in to reply
 

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