Theoretically we can use map to optimize the search process, but why it is still slower than linear search? Is it because of the test case?! The map should be like binary search, right? But the result show that the first(linear search) is 24ms and the second(using map) is 40ms.

First:

```
ListNode* insertionSortList(ListNode* head) {
ListNode sentinel(0), *prev = nullptr, *cur = head;
while (cur) {
if (!prev || !prev->next || prev->next->val > cur->val) prev = &sentinel;
while (prev->next && prev->next->val < cur->val) {
prev = prev->next;
}
ListNode *tmp = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = tmp;
}
return sentinel.next;
}
```

Second:

```
ListNode* insertionSortList(ListNode* head) {
ListNode sentinel(0), *cur = head;
map<int, ListNode*> cache;
cache[INT_MIN] = &sentinel;
while (cur) {
ListNode *p = (--cache.upper_bound(cur->val))->second;
cache[cur->val] = cur;
ListNode *tmp = cur->next;
cur->next = p->next;
p->next = cur;
cur = tmp;
}
return sentinel.next;
}
```

Is it because of the test case?!