I implement the solution by regular insert sort (in time of O(n^2)), but it cant be accepted due to TLE. I'm wondering if there is better time consuming insert sort?

Here is my code. I think it's very intuitive. I track the original list by "it", and compare it to all sorted elements which is iterated by "cmp". To implement insertion, I also maintain a pointer "precmp" to hold the position for insertion.

```
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(!head) return 0;
ListNode * dummy=new ListNode(-65535);
dummy->next=head;
head=dummy;
ListNode *it=head;
ListNode *cmp=head;
while(it->next!=NULL){
ListNode *pre=it;
it=it->next;
ListNode *precmp=head;
cmp=head->next;
while(cmp!=it && cmp->val <= it->val){
precmp=cmp;
cmp=cmp->next;
}
if(cmp!=it){
pre->next=it->next;
precmp->next=it;
it->next=cmp;
}
}
return dummy->next;
}
};
```