C++ Very elegant 12 Lines 388ms


  • 0
    R

    The first solution has good space complexity equal O( number of lists ).
    The second solution has worst space complexity O( number of elements) but is faster(388ms) because it uses the std::vector to sort the elements.

    //
    // First solution
    //

       ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
    
        auto comp = [] ( ListNode* y, ListNode* x) { return  !x || y && x->val < y->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> queue( comp  , lists );
        
        ListNode dummy(0);
        ListNode* node = &dummy;
        
        while (! queue.empty())
        {
            ListNode* smallest = queue.top();
            queue.pop();
            node->next = smallest;
            if (smallest)
            {
                node = smallest;
                queue.push(smallest->next);
            }
        }
        
        return dummy.next;
    }
    

    //
    // Second solution
    //

    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        vector<ListNode*> v;
        
        for (auto list : lists)
        {
            while (list)
            {
                v.push_back(list);
                list = list->next;
            }
        }
        
        sort( v.begin(), v.end(), [] ( ListNode* x, ListNode* y) { return  !x || y && x->val < y->val;} );
        
        ListNode dummy(0);
        ListNode* node = &dummy;
        
        for ( auto next : v )
        {
            node->next = next;
            node = node->next;
        }
        
        node->next = 0;
        return dummy.next;
    }

  • 1
    R

    merge is better than sort, because it is sorted already!


  • 0
    T

    Agreed, rantos22 is essentially converting the k linked lists into a huge array list and then sorting that.


  • 0
    T

    n is the total number of elements, k is the number is lists.
    The time complexity for the 1st is O(n * log k) and the space is O(k).
    The time complexity for the 2nd is O(n log n) the space is O(n).
    There are also 2 n iterations in the second one.


  • 0
    R

    https://www.youtube.com/watch?v=YQs6IC-vgmo

    Arrays have better cache locality though which means better constant factor. That's why copying to an array and sorting ends up faster.


  • 0
    T

    Thanks for the video, it's interesting. How much faster is the second solution? (there's only one ms value above: 388).

    I'm asking because his whole point is that if you store the Point structure in a vector compactly you get better locality, but you're not doing anything similar to that. You're storing pointers whose locality is awesome, but when sorting you still get O(n log n) cache misses because each comparison has to go and find the ListNode.val on the heap.


  • 0
    T

    In the second solution you're checking for null in the comparator, but not when re-linking the list. Which I guess proves that there are no nulls in any of the inputs :)


  • 0

    For your 2nd solution, why do you need "node->next = 0" just before you return? What's the purpose of that? Thanks


  • 0
    T

    It makes sure that the last node points to null, I guess it's not necessary for this problem statement, because the last node will be the last node of one of the lists.

    That solution is more generic, it also works on non-sorted input, in which case the biggest node may be from inside one of the lists and hence has a valid next pointer that would lead to a cycle in the result. Also in case of empty input it makes sure that the return value is null and not garbage: notice that node may be just an alias for dummy.


Log in to reply
 

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