20.11.20 leetcode147

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if( head== nullptr )return head;
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* sortedNode=head,* curr=head->next;
        while(curr!=nullptr){
            if(sortedNode->val<=curr->val)sortedNode=sortedNode->next;
            else{
                ListNode* pre=dummyHead;
                while(pre->next->val<=curr->val)pre=pre->next;
                sortedNode->next=curr->next;
                curr->next=pre->next;
                pre->next=curr;
            }
            curr=sortedNode->next;
        }
        return dummyHead->next;
    }
};