My c++ solution use a modified heap sort


  • 0
    L
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    	vector<ListNode*> ls;
            ListNode* dummy = new ListNode(0);
            ListNode* curr = dummy;
    	for(auto l:lists)	
                    if(l!=NULL)	ls.push_back(l);
    	int n = ls.size();
    	if(n==0)	return NULL;
    	if(n==1)	return ls[0];
    	buildHeap(ls,n);
    	while(n>0){
    		ListNode* thismax = getAndUpdateMin(ls,n);
    		curr->next = thismax;
    		curr = curr->next;
            }
            return dummy->next;
    }
    
    void buildHeap(vector<ListNode*>& ls, int n){
    	for(int i = (n-1)/2;i>=0;i--){
    		siftDown(ls,i,n);
        }
    }
    
    ListNode* getAndUpdateMin(vector<ListNode*>& ls, int& n){
    	ListNode* mx = ls[0];
    	ls[0] = ls[0]->next;
    	if(ls[0] == NULL){
    		swap(ls[0],ls[n-1]);
                    ls.pop_back();
                    n--;
    		siftDown(ls,0,n);
    	}
    	else{
    		siftDown(ls,0,n);
        }
    	return mx;
    }
    
    void siftDown(vector<ListNode*>& ls, int index, int n){
    	if(index >= n/2)	return;
    	int leftchild = index*2 + 1;
    	int tmp = index;
    	int rightchild = index*2 + 2;
    	if(leftchild < n &&ls[leftchild]->val < ls[tmp]->val){
    		tmp = leftchild;
            }
    	if(rightchild < n &&ls[rightchild]->val < ls[tmp]->val){
    		tmp = rightchild;
            }
    	if(index != tmp)	{
                    swap(ls[tmp],ls[index]);
                    siftDown(ls,tmp,n);
        }
    }
    
    

Log in to reply
 

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