My 16 lines C++ solution using "MULTIMAP", but it's not fast. Can anyone teach me to speed it up ?


  • 0
    V

    class Solution {

    public:

    ListNode* sortList(ListNode* head) {
        if(head == nullptr){
            return nullptr;
        }
        ListNode *node = head;
        multimap<int, ListNode*> m;
        // use multimap to store and sort
        while(node != nullptr){
            m.insert(pair<int, ListNode*>(node->val, node));
            node = node->next;
        }
        // connect nodes reversly
        ListNode* j = nullptr;
        map<int, ListNode*>::reverse_iterator i;
        for(i = m.rbegin(); i != m.rend(); i++){
            i->second->next = j;
            j = i->second;
        }
        return m.begin()->second; 
    }
    

    };


Log in to reply
 

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