- add a temp haed;
- divide the list into two parts: sort part and unsort part;
- use a map to find the insert place fast
- 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;
}
```