Share my C++ solution running in 48ms


  • 0
    A
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
             multimap<int, int> mii;
             ListNode *head = nullptr, *p;
             for(int i=0; i<lists.size(); i++) {
                 if(lists[i]) mii.insert( make_pair(lists[i]->val, i) );
             }
             while( !mii.empty() ) {
                 int k = mii.begin()->second;
                 p = lists[k];
                 lists[k] = p->next;
                 p->next = head;
                 head = p;
                 mii.erase( mii.begin() );
                 if(lists[k]) mii.insert( make_pair(lists[k]->val, k) ); 
                 
             }
             head = reverseList(head);
             return head;
        }
        
        ListNode* reverseList(ListNode* head) {
            ListNode *pre = head, *newHead = nullptr, *p;
            while(pre) {
                p = pre;
                pre = pre->next;
                p ->next = newHead;
                newHead = p;
            }
            
            return newHead;
            
        }
    };
    

    My solution could be accepted and runtime is 48 ms.


Log in to reply
 

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