Time complexity O(n). C++ code without recursive and Priority-Queue


  • -1
    S

    By creating an extra node with val equaling INT_MAX,we can do it within O(sum(length of every list)) time complexity and O(lists.size())

    	ListNode* mergeKLists(vector<ListNode*>& lists) {
    		if (lists.size() == 0) return NULL;
    		for (int i = 0; i < lists.size(); ++i) {
    			if (!lists[i])
    			{
    				lists[i] = new ListNode(INT_MAX);
    			}
    			else {
    				ListNode *pt = lists[i];
    				while (pt->next) pt = pt->next;
    				pt->next = new ListNode(INT_MAX);
    			}
    		}
    
    		vector<ListNode*> pts(lists);
    		ListNode preHead = ListNode(INT_MIN);
    		ListNode *cur = &preHead;
    		while (true) {
    			int min = INT_MAX;
    			int minLoc = -1;
    			for (int i = 0; i < pts.size(); ++i) {
    				if (pts[i]->val <= min) {
    					min = pts[i]->val;
    					minLoc = i;
    				}
    			}
    
    			if (!pts[minLoc]->next) {
    				cur->next = NULL;
    				break;
    			}
    			cur->next = pts[minLoc];
    			cur = cur->next;
    			pts[minLoc] = pts[minLoc]->next;
    		}
    
    		return preHead.next;
    	}
    

Log in to reply
 

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