【leetcode】147. Insertion Sort List

Sort a linked list using insertion sort.

链表的插入排序。

需要创建一个虚拟节点。注意点就是不要节点之间断了。

class Solution {
public:

    ListNode* insertionSortList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode* newhead = new ListNode(-2147483648);
        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;      
    }
};