32 ms C++ solution


  • 1
    I

    In order to make it faster, do it a divide-and-conquer way: merge ListNodes pairwise and you will have n/2 ListNodes, then merge them again pairwise and you will have n/4 ListNodes, and so on...

    /**
     * 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) {
            if (lists.size() == 0) {
                return NULL;
            }
            if (lists.size() == 1) {
                return lists.at(0);
            }
            vector<ListNode*> newlists;
            while (lists.size() > 1) {
                newlists.clear();
                for (int i = 0; i < lists.size() / 2; i ++) {
                    ListNode* result = mergeTwo(lists.at(2 * i), lists.at(2 * i + 1));
                    newlists.push_back(result);
                }
                if (lists.size() > 2 * (lists.size() / 2)) {
                    newlists.push_back(lists.at(lists.size() - 1));
                }
                lists = newlists;
                //cout << lists.size() << " size of the lists" << endl;
            }
            return newlists.at(0);
        }
        
        ListNode* mergeTwo(ListNode* a, ListNode* b) {
            ListNode* merged = NULL;
            if (a == NULL and b == NULL) {
                return merged;
            }
            else if (a == NULL and b != NULL) {
                merged = b;
            }
            else if (a != NULL and b == NULL) {
                merged = a;
            }
            else {
                ListNode* current1 = a;
                ListNode* current2 = b;
                merged = new ListNode(0);
                ListNode* current = merged;
                while (current1 != NULL or current2 != NULL) {
                    if (current1 == NULL and current2 != NULL) {
                        current->next = current2;
                        current = current->next;
                        current2 = current2->next;
                    }
                    else if (current1 != NULL and current2 == NULL) {
                        current->next = current1;
                        current = current->next;
                        current1 = current1->next;
                    }
                    else {
                        if (current1->val < current2->val) {
                            current->next = current1;
                            current = current->next;
                            current1 = current1->next;
                        }
                        else {
                            current->next = current2;
                            current = current->next;
                            current2 = current2->next;
                        }
                    }
                    //cout << "current val " << current->val << endl;
                }
                merged = merged->next;
            }
            return merged;
        }
    };
    

Log in to reply
 

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