Easy to understand C++ solution with no extra memory consumption


  • 0
    F

    An easy to understand solution in C++. Complexity proportional to O(k*l), where k = number of lists, and l = length of the largest list. No extra space used.

    class Solution {
    private:
        struct key_t{
            int val;
            int idx;
            key_t() : val(0), idx(0) {}
        };
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size() == 0) return NULL;
            
            ListNode* merger = 0;
            ListNode* front = 0;
            
            key_t key;
            key.val = INT_MAX;
            
            while(true) {
                for (int i = 0; i < lists.size(); ++i) {
                    if(lists[i] == NULL) { // reached the end?
                        continue;
                    }
                    if(lists[i]->val < key.val) {
                        key.val = lists[i]->val;
                        key.idx = i;
                    }
                }
                if(key.val == INT_MAX) { // done?
                    break;
                }
                // add a new node with min found
                if(merger == NULL) {
                    merger = new ListNode(key.val);
                    front = merger;
                } else {
                    merger->next = new ListNode(key.val);
                    merger = merger->next;
                }
                    
                // advance the list[i] pointer
                lists[key.idx] = lists[key.idx]->next;
                // reset 
                key.val = INT_MAX;    
            }
            return front;
        }
    };
    

Log in to reply
 

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