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

  • 0
    #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 {
    	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;
    		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();
    		 	if (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.