Sharing my straightforward C++ solution without data structure other than vector


  • 92
    Z
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty()){
            return nullptr;
        }
        while(lists.size() > 1){
            lists.push_back(mergeTwoLists(lists[0], lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists.front();
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        if(l1->val <= l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    

    The second function is from Merge Two Sorted Lists.

    The basic idea is really simple. We can merge first two lists and then push it back. Keep doing this until there is only one list left in vector. Actually, we can regard this as an iterative divide-and-conquer solution.


  • 1
    C

    nice work. what about the time?


  • 69
    L

    check my c++ solution, without using push_back, erase, which is time consuming,
    use only 34ms

    class Solution {
    public:
        ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (NULL == l1) return l2;
            else if (NULL == l2) return l1;
            if (l1->val <= l2->val) {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
            else {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            if (lists.empty()) return NULL;
            int len = lists.size();
            while (len > 1) {
                for (int i = 0; i < len / 2; ++i) {
                    lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
                }
                len = (len + 1) / 2;
            }
            
            return lists.front();
        }
    };

  • 3
    Z

    is the time complexity of this algo is kn(lgk), assuming the length of every list is n.


  • 0
    M

    Your solution deserves more attention!!!


  • 1
    X

    I think the running time should be O(n^2k), because as merge keep going, the length of a list could grow to as large as nk, and the merge two sorted lists will be called n-1 times. Thus it is nk(n-1) -> O(n^2*k)


  • 1
    L

    I use the same idea, and find it need 404ms, not 34ms. I copy your code and get the time 416ms too!


  • 0
    L

    I just submitted the code again, and I get 428ms. But one month ago, it is 34ms. I think something is changed to the OJ


  • 0
    L

    I see, Thanks for your reply! Your solution looks much more simple than mine with the similar idea. It helps me a lot.


  • 1

    The idea is almost the same, and my JS solution ends up like this :)

    /**
     * Memo: Treat lists as a queue and pop two lists and merge them, then append the new list until there is only one list left.
     * TODO the mergeTwoLists could be improve as the list is almost sorted already.
     * Complex: O(n^2*k)
     * Runtime: 212ms
     * Tests: 130 test cases passed
     * Rank: S
     * Updated: 2015-06-20
     */
    
    var mergeKLists = function(lists) {
        var mergeTwoLists = function(h1, h2) {
            var dummy = new ListNode(null);
            var tail = dummy;
            while (h1 && h2) {
                if (h1.val <= h2.val) {
                    tail = tail.next = h1;
                    h1 = h1.next;
                } else {
                    tail = tail.next = h2;
                    h2 = h2.next;
                }
            }
            tail.next = h1 ? h1 : h2;
            return dummy.next;
        };
    
        if (!lists || lists.length === 0) return null;
        while (lists.length > 1) lists.push(mergeTwoLists(lists.shift(), lists.shift()));
        return lists[0];
    }

  • 0
    F

    can i ask why len = (len + 1) / 2;??


  • 0
    R

    hi, I liked your code, what is the complexity? logk*n ?


  • 0
    B
    This post is deleted!

  • 0
    C

    yes, i think so.


  • 0
    W

    because every time merge half of the whole lists, and put the result to the first half of the lists, so the next time, all the merged lists are in the first half of the vector.


  • 0
    V

    I don't think so......you should know the length of a list grows from n to kn,not always kn;
    every time the length grows two times, so the length from n to kn cost logk ,every time all the nodes are kn, so the total is kn*logk


  • 0
    D

    方法不错,为啥你们都用英文。。。


  • 0
    H

    Actually, is O(nk^2). There are (k - 1) merge, with (i + 1) * n as the cost of the i-th merge. And hence, the complexity is:

    O(2n + 3n +... + kn) = O(n(2 +... + k)) = (nk^2)


  • 0
    L

    哈哈,感觉leetcode已经被国人刷屏了


  • 5
    C

    Suppose initially each list is of average length n, then:
    k/2*(2n) + k/4*(4n) + k/8*(8n)... + = logk * (kn)


Log in to reply
 

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