26ms C++11-ish code extensively using <algorithm>


  • 0
    X
    #include <algorithm>
    #include <vector>
    
    bool cmp( ListNode* n1,  ListNode* n2 ) {
        // > to make the min heap
    	return n1->val > n2->val;
    }
    
    bool isNonNull( ListNode *n) {
    	return n;
    }
    
    using namespace std;
    
    class Solution {
    public:
    	ListNode* mergeKLists(vector<ListNode*>& lists) {
    
    		//avoid null heads in test set
            //tried to use std::erase(remove_if(...)) but was very slow
    		std::vector<ListNode*> v;
    		v.reserve(lists.size());
    		copy_if(lists.begin(), lists.end(), back_inserter(v), isNonNull);
    		if (v.empty()) return nullptr;
    
     		ListNode * head = new ListNode(-1); //a placeholder head
     		ListNode * curr = head;
    
     		make_heap(v.begin(), v.end(), cmp);
    		while(!v.empty()) {
    			//at begin of the loop, v is a valid heap
    		 	pop_heap(v.begin(), v.end(), cmp);
    		 	ListNode * newNode = v.back();
    		 	v.pop_back();
    		 	if (newNode->next) {
    		 		v.push_back(newNode->next);
    		 		push_heap(v.begin(), v.end(), cmp);
    		 	}
    
    		 	curr->next = newNode;
    		 	curr = newNode;
    		 }
    
    		 curr = head->next;
    		 delete head;
    		 return curr;
    	}
    };
    

Log in to reply
 

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