class Solution {

public:

    ListNode* insertionSortList(ListNode* head) {

        if(head==NULL||head->next==NULL)

            return head;

        ListNode* newhead = new ListNode(-);

        newhead->next=head;

        ListNode* q=head;

        ListNode* p=head->next;

        while(p!=NULL){

            ListNode* s1=newhead;

            ListNode* s2=s1->next;

            while(s2!=p&&s2->val<=p->val){

                s1=s2;

                s2=s2->next;

            }

            if(s2!=p){

            s1->next=p;

            q->next=p->next;

            p->next=s2;

            p=q->next;}

            else{

                q=p;

                p=p->next;

            }

        }

        return newhead->next;

    }

};