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

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)

// 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;
}``````

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