Elegan solution based on a heap of lists ;-)


  • 11
    R

    I convert the vector of lists into an heap and I use it to generate the merged list:

    class Solution {
        
    public:
        
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            
            // Begin and end of our range of elements:
            auto it_begin = begin(lists);
            auto it_end = end(lists);
            
            // Removes empty lists:
            it_end = remove_if(it_begin, it_end, isNull);
            if (it_begin == it_end) return nullptr; // All lists where empty.
            
            // Head and tail of the merged list:
            ListNode *head = nullptr;
            ListNode *tail = nullptr;
            
            // Builds a min-heap over the list of lists:
            make_heap(it_begin, it_end, minHeapPred);
            
            // The first element in the heap is the head of our merged list:
            head = tail = *it_begin;
            
            while (distance(it_begin, it_end) > 1) {
                
                // Moves the heap's front list to its back:
                pop_heap(it_begin, it_end, minHeapPred);
                
                // And removes one node from it:
                --it_end;
                *it_end = (*it_end)->next;
                
                // If it is not empty it inserts it back into the heap:
                if (*it_end) {
                    
                    ++it_end;
                    push_heap(it_begin, it_end, minHeapPred);
                }
                
                // After  the push we have our next node in front of the heap:
                tail->next = *it_begin;
                tail = tail->next;
            }
            
            return head;
        }
        
    private:
        
        // Predicate to remove all null nodes from a vector:
        static bool isNull(const ListNode* a) {
            
            return a == nullptr;
        }
    
        // Predicate to generate a min heap of list node pointers:
        static bool minHeapPred(const ListNode* a,
                                const ListNode* b) {
    
            assert(a);
            assert(b);
            
            return a->val > b->val;
        }
        
    };

  • 6
    S

    I have a similar idea by using a min heap to switch in the lists. But I keep two min values each run so one list can keep attached until its value exceeds the second min value (from another list). In this way, it avoids to update the heap since we know the new min value is still from the current active list. Therefore, the overall time is still O(nlogk) in worst case yet hopefully has a better average time complexity. The best case is O(n) which has a constant heap updating, for example, list 1 is all smaller than list 2, and list 2 is all smaller than list 3 and so on so forth.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            // simple cases
            int k = lists.size();
            if (k == 0)
                return NULL;
            else if (k == 1)
                return lists[0];
                
            // data structure for return list
            ListNode dummy(0);
            ListNode * head = &dummy;
            ListNode * tail = head;
            
            // maintain a heap for minimum emlements, one from each list
            map<pair<int, int>, ListNode*> minNodes;
            for (int i = 0; i < k; i++) {
                if (lists[i] != NULL)
                    minNodes[pair<int, int>(lists[i]->val, i)] =lists[i];
            }
            
            // attach elements from the list with the minimum value until it
            // exceeds the next minimum value from another list
            while (!minNodes.empty()) {
                pair<int, int> curMin = minNodes.begin()->first;
                ListNode* pNode = minNodes.begin()->second;
                minNodes.erase(minNodes.begin());
                
                // the last list case
                if (minNodes.empty()){
                    tail->next = pNode;
                }
                else {
                    // add new nodes to result until reach to the next min value
                    pair<int, int> nexMin = minNodes.begin()->first;
                    while (pNode != NULL && pNode->val <= nexMin.first) {
                        tail->next = pNode;
                        tail = tail->next;
                        pNode = pNode->next;
                    }                
                
                    // update the minimum entry in the minNodes list
                    // note that, the heap updating not happen on each scanned node
                    if (pNode != NULL)
                         minNodes[pair<int, int>(pNode->val, curMin.second)] = pNode;
                }
            }
            
            return head->next;
        }
    };

  • 0
    R

    You had a great point.
    i think putting together our two solution would create a great one.
    I think it is better to create the heap in-place in the whole vector because would minimize ops, but getting the second element from an heap in order to insert as muche element as possible from the first list is a huge hit.


  • 0
    S

    I agree with you, in-place heap is a plus!


  • 0
    R

    Now the problem is: how to efficiently have the first two elements of a priority queue with an in-place heap?

    We know that 99.9% of cases a binary heap is used, but the standard does not specify it.
    We can build an heap from the second element and manually compare with the first or implement our heap methods. The second is funnier ;-)


  • 0
    S

    I am not sure how to do this. It seems to me that each time remove the first element from the heap then get the next element works fine. :)


  • 0
    Q

    I write it using python ,but get TLE, I am wondering why,is it taking long time for python to run because python is slower?


  • 0
    Z
    This post is deleted!

Log in to reply
 

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