I haven't seen clear C++ solution in the discussions, so paste my passed code. The idea is of no trick as following:

(1) As a special case, break the 1st node from the input linkedlist as the 1st node of output linkedlist, then the head pointer of the input linkedlist is pointed to its second node,

(2) keep breaking nodes from the remaining input linkedlist and insert this node to the *correct* position of the output linkedlist. The correct insert position may be at the beginning, or in the middle(end).

```
ListNode * insertionSortList(ListNode * head)
{
if (!head)
return NULL;
//first node
ListNode * resultHead = head;
head = head->next;
resultHead->next = NULL;
//remaining nodes
while (head)
{
ListNode * toInsert = head;
head = head->next;
if (toInsert->val < resultHead->val) //insert to beginning
{
toInsert->next = resultHead;
resultHead = toInsert;
}
else //insert to middle or end
{
ListNode * current = resultHead;
while ((current->next)&&(current->next->val < toInsert->val))
current = current->next;
toInsert->next = current->next;
current->next = toInsert;
}
}
return resultHead;
}
```