insertion-sort-list

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(!head||!head->next)return head;
        ListNode*sortedList=new ListNode(-1);
        ListNode*cur=head;
        while(cur){
            ListNode*next=cur->next;
            ListNode*node=sortedList;
            while(node->next&&node->next->val<cur->val)
            {
                node=node->next;
            }
            cur->next=node->next;
            node->next=cur;
            cur=next;
        }
        return sortedList->next;
    }
};