Using min heap w/ functor OR lambda function - concise code - with few comments

  • 0

    Algo works like this: store all k first elements from the lists in a min heap, store the min somewhere, replace it with another node from the list

    ListNode* mergeKLists(vector<ListNode*>& lists) {

    Using Lambda function

        auto cmp = [](ListNode* left, ListNode* right) { return (left->val) > (right->val);};
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>heap(cmp);

    Or using functor- This seemed to have 4ms slowdown compared to lambda function

        struct cmp{ bool operator()(ListNode* left, ListNode* right){return (left->val) > (right->val);}};
        priority_queue<ListNode*, vector<ListNode*>,cmp>heap;
        //maintain a k-ary heap
        for(int i=0; i<lists.size();i++){
        ListNode *root = new ListNode(0);
        ListNode *tail = root;
        //create the resulting list
            ListNode *tmp =; heap.pop();
            tail->next = new ListNode(tmp->val);
            tail = tail->next;
        return root->next;

Log in to reply

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