There are two tricks here to simplify the programming

- use a dummy node to track the new link head;
- always save the last sorted val (i.e. prev). check if the current unsorted node has a value larger than "prev", if so, we just need to search the current insert position from the previous insert position (start); otherwise, let's search from the beginning (Dummy)

```
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode Dummy(INT_MIN); // dummy node to track the new head
ListNode *start = &Dummy, *temp; // the insert position
int prev = INT_MAX; // the value of the last sorted node
while(head)
{
if(prev > head->val) start = &Dummy; // if the last sorted node has a larger value than the current one, then we have to search from the beginning
prev = head->val;// update prev to the current node value
while(start->next && start->next->val <= head->val) start = start->next; // search the insert position
temp = start->next;
start->next = head;
head = head->next;
start->next->next = temp;
}
return Dummy.next;
}
};
```