Brief C++ solution with priority_queue


  • 16
    C

    We just need to define a comparison struct for ListNodes, then managing the priority_queue is quite straightforward. After filling the priority_queue, if it is non-empty, we set the head and tail. Then we repeatedly pop the top off the queue and append that to the tail. If the next node is not null, we push it onto the queue.

    class Solution {
        struct compare {
            bool operator()(const ListNode* l, const ListNode* r) {
                return l->val > r->val;
            }
        };
        
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            priority_queue<ListNode *, vector<ListNode *>, compare> q;
            for (auto l : lists) {
                if (l) {
                    q.push(l);
                }
            }
            
            if (q.empty()) {
                return NULL;
            }
            
            ListNode* result = q.top();
            q.pop();
            if (result->next) {
                q.push(result->next);
            }
    
            ListNode* tail = result;            
            while (!q.empty()) {
                tail->next = q.top();
                q.pop();
                tail = tail->next;
                if (tail->next) {
                    q.push(tail->next);
                }
            }
            
            return result;
        }
    };

  • 11
    C

    little refine to make it shorter :)

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        std::priority_queue<ListNode*, std::vector<ListNode*>, mycomparison > heap;
        ListNode head(0);
        ListNode *curNode = &head;
        int i, k, n = lists.size();
        for (i = 0; i < n; i++)
            if (lists[i]) heap.push(lists[i]);
        while (!heap.empty()){
            curNode->next = heap.top();
            heap.pop();
            curNode = curNode->next;
            if (curNode->next) heap.push(curNode->next);
        }
        return head.next;
    }

  • 0
    C

    Nice. The trick of constructing a helper head node makes a lot of linked list algorithms much simpler.


  • 0
    M

    It's close to my solution. But I found using priority_queue is quite slow and my runtime is 430ms.


  • 2
    M

    Until I see the first answer written by cfjmonkey, I'm confused with heap and priority_queue version solution of this problem. Rewrite it by using make_heap. Now it's easy to see the difference.

    ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
        ListNode head(0);
        ListNode *curNode = &head;
        vector<ListNode*> v;   
        for(int i =0; i<lists.size(); i++){
            if (lists[i]) v.push_back(lists[i]);
        }
        make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture
        
        while(v.size()>0){
            curNode->next=v.front();
            pop_heap(v.begin(), v.end(), heapComp); v.pop_back(); 
            curNode = curNode->next;
            if(curNode->next) {
                v.push_back(curNode->next); 
                push_heap(v.begin(), v.end(), heapComp);
            }
        }
        return head.next;
    }
    static bool heapComp(ListNode* a, ListNode* b) {
            return a->val > b->val;
    }

  • 0
    K

    Dude, you are alive! @ChiangKaiShrek


  • 4

    Nice implementation .
    Here are some example how to use the compare-component-function

    -Method 1 -

           std::priority_queue<int, std::vector<int>, decltype(&compare)> pq(&compare);
    

    The compare can be any your defined function

    -Method 2-

    You can use the default less function

         std::priority_queue<int, std::vector<int>, std::less<int> > pq;
    

    -Method 3-

    You can use the lamda-expression

       auto comp = [] (int &a, int &b) -> bool { return a < b; };
      std::priority_queue<int,std::vector<int>, decltype(comp) > pq (comp);

  • 0
    N

    the default comp is less<T>, why compare is l->val > r->val instead of l->val < r->val


  • 0
    Y

    use a dummy node so you don't have to one extra iteration outside of while loop.


  • 0
    Y
    class Solution {
        struct compare {
            bool operator()(const ListNode* l, const ListNode* r) {
                return l->val > r->val;
            }
        };
    
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            priority_queue<ListNode *, vector<ListNode *>, compare> q;
            for (auto l : lists) 
                if (l)
                    q.push(l);
                    
            ListNode* dummy = new ListNode(0);     
            ListNode* tail=dummy;
            while (!q.empty()) {
                tail->next = q.top();
                q.pop();
                tail = tail->next;
                if (tail->next) {
                    q.push(tail->next);
                }
            }
    
            return dummy->next;
        }
    };

  • -1
    L

    you forget to delete dummy before return...


  • 0
    N

    Can I ask you a question about c++,

    bool operator()(const ListNode* & l, const ListNode* & r) {
                return l->val > r->val;
            }
    

    why I cannot add & ?


  • 0
    J

    @meow- I think that is probably because you try to insert every element into priority queue first. If you only insert the first element of every lists and call top() and pop() of priority queue, it is pretty fast.


Log in to reply
 

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