[C++] 26ms Q based non-recurrsion beat 92%


  • 1
    D

    Here is what we want to do:

    list1, list2, list 3, list 4............. list k
       \      /         \    /
        list1'         list2' .....
           \              /
               list 1'' .....

    Quite obvious, we are doing a reverse "tree by level traverse". With help of a queue, we can achieve O(nlgk) easily. The queue initially contains all input lists. We dequeue 2 lists every time, merge them then put the result back until the queue contains only one list which is the result.

    Please note the 2 checks in mergeTwoLists() function. They reduce run time by 50%.

    26ms. Beat 91.75%.

    BTW, doing "erase()" etc. operations against "lists" parameter is a bad idea:

    1. You should not alter the content of the parameter if not specifically instructed.
    2. erase() is a O(n) operation for a vector.
    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            if (lists.size() == 0) {
                return NULL;
            }
    
            queue<ListNode *> q;
            for (auto n : lists) {
                q.push(n);
            }
    
            while (q.size() > 1) {
                ListNode *l1 = q.front();
                q.pop();
                ListNode *l2 = q.front();
                q.pop();
                q.push(mergeTwoLists(l1, l2));
            }
    
            return q.front();
        }
    
    // TL;DR
    private:
        ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
            if (list1 == NULL) {
                return list2;
            }
            else if (list2 == NULL) {
                return list1;
            }
    
            ListNode dummy(0);
            ListNode* current = &dummy;
    
            while (list1 != NULL && list2 != NULL) {
                if (list1->val <= list2->val) {
                    current->next = list1;
                    list1 = list1->next;
                }
                else {
                    current->next = list2;
                    list2 = list2->next;
                }
    
                current = current->next;
            }
    
            if (list1 != NULL) {
                current->next = list1;
            }
    
            if (list2 != NULL) {
                current->next = list2;
            }
    
            return dummy.next;
        }
    };
    

Log in to reply
 

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