C++ solution with map, O(nlogn) time


  • 0
    1. add a temp haed;
    2. divide the list into two parts: sort part and unsort part;
    3. use a map to find the insert place fast
    4. insertion sort

    Because map in c++ is O(logn), so the time complexity is O(nlogn)

    ListNode *insertionSortList(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return head;
        
        // add a temp haed
        ListNode *h = new ListNode(0);
        h -> next = head;
    
        // divide the list into two parts: sort part and unsort part
        ListNode *rem = h -> next -> next;
        h -> next -> next = NULL;
        
        // map is used to find the insert place fast
        map<int, ListNode *> hash;
        hash[h -> next -> val] = h -> next;
        
        // insertion sort
        while(rem != NULL)
        {
            ListNode *p = NULL;
            
            // find the insert place
            auto it = hash.find(rem -> val);
            if(it == hash.end())
            {
                hash[rem -> val] = rem;
                it = hash.find(rem -> val);
                p = it == hash.begin() ? h : (-- it) -> second;
            }
            else
            {
                p = it -> second;
                hash[rem -> val] = rem;
            }
            
            // insert node
            ListNode *temp = rem -> next;
            rem -> next = p -> next;
            p -> next = rem;
            rem = temp;
        }
        
        return h -> next;
    }

Log in to reply
 

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