Reference from https://discuss.leetcode.com/topic/14916/explained-c-solution-24ms, which is quite clear description:

"First, a quick recap of insertion sort:

Start from the second element (simply a[1] in array and the annoying head -> next -> val in linked list), each time when we see a node with val smaller than its previous node, we scan from the head and find the position that the current node should be inserted. Since a node may be inserted before head, we create a new_head that points to head. The insertion operation, however, is a little easier for linked list."

```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head)
{
if(head == NULL) return NULL;
ListNode* newhead = new ListNode(0);
newhead->next = head;
ListNode* before = head;
ListNode* current = head->next;
while(current != NULL)
{
if(before->val > current->val)
{
before->next = current->next;
if(newhead->next->val > current->val)
{
current->next = newhead->next;
newhead->next = current;
}
else
{
ListNode* temp = newhead;
while(temp->next != before)
{
temp = temp->next;
if(temp->next->val > current->val)
{
current->next = temp->next;
temp->next = current;
break;
}
}
}
current = before->next;
}
else
{
before = before->next;
current = before->next;
}
}
head = newhead->next;
delete newhead;
return head;
}
};
```