The insertion sorting is quite trivial: starting from head, insert each node to the new sorted linked list.

Step 1) find the inserting position (i.e. move cur to the position just before head)

Step 2) insert head node in between of cur and cur->next;

Step 3) move head to the next one

Here, we use a dummy node to track the head of the sorted list.

```
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN), *cur=&dummy, *temp;
while(head)
{ //go through each node in the list
for(cur = &dummy; cur->next && cur->next->val<head->val; ) cur = cur->next; //step 1
temp = head->next;
head->next = cur->next;
cur->next =head; //step 2
head = temp; //step 3
}
return dummy.next;
}
};
```

The above one has ~80ms performance. One trick to optimize it is that: in the above version, every time we insert a new node, we always search the inserting position from the beginning of the sorted list (i.e. in step1 for(cur = &dummy;...) and that is not neccessary. If the new to-be-inserted node has a value larger than the value of the last inserted node, then that means the inserting position is after the inserting position found in the previous iteration, so we can use cur from the previous iteration directly. So we include

```
if(cur->val>head->val) cur = &dummy; // trick, reset cur only when needed
```

to reset cur to the start of the sorted list only when needed. This speeds up the algorithm to 24ms.

```
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN), *cur=&dummy, *temp;
while(head)
{
if(cur->val>head->val) cur = &dummy; // trick, reset cur only when needed
for(; cur->next && cur->next->val<head->val; )
cur = cur->next;
temp = head->next;
head->next = cur->next;
cur->next =head;
head = temp;
}
return dummy.next;
}
};
```