class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(!head) return NULL;
// add new node with INT_MIN
ListNode* newHead = new ListNode(INT_MIN);
newHead>next = head;
// loop every node
for(ListNode*p = head>next, *prep = head; p; prep = p, p=p>next)
{
// insert them to the right position of link list
for(ListNode * cur = newHead; cur>next!=p; cur = cur>next)
{
if (cur>next>val > p>val)
{
// insert between cur * cur>next
prep>next = p>next;
p>next = cur>next;
cur>next = p;
p = prep;
break;
}
}
}
ListNode* result = newHead>next;
delete newHead;
return result;
}
};
Accepted insertion sort list


I think the following solution is better without using new nodes:
class Solution { public: ListNode *insertionSortList(ListNode *head) { if(head==NULL  head>next==NULL) return head; ListNode *cur = head; while(cur) { ListNode *tmp = cur>next; while(tmp) { if(tmp>val < cur>val) { int a = tmp>val; tmp>val = cur>val; cur>val = a; } tmp = tmp>next; } cur = cur>next; } return head; } };

Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example