Insertion Sort List

Sort a linked list using insertion sort.

注意：

1.当新链表要插入最小值时，即插入一个新的头结点，那么原来的指向头结点的指针要更换。sortedList=s;使得sortedList指针也指向s所指的节点。（s为新头结点）

2.注意q和preq的关系，插入最大结点时，preq为最后一个结点，而q为NULL，所以循环条件是q!=NULL

代码更新，其实只需新建一个虚拟的头结点sortedHead，那么可以使得我们的插入操作变得更加简单，不再需要区分插入头部，还是插入中间或者尾部。

0x80 00 00 00是32位机中int的最小值

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL) return NULL;
        ListNode* p=head;
        
        ListNode* sortedHead=(ListNode*)malloc(sizeof(ListNode));
        sortedHead->val=0x80000000;
        sortedHead->next=NULL;
        ListNode* s=(ListNode*)malloc(sizeof(ListNode));
        s->val=p->val;
        sortedHead->next=s;
        s->next=NULL;

        ListNode* preq=sortedHead;
        ListNode* q=sortedHead->next;

        while(p->next!=NULL){
            p=p->next;
            while(q!=NULL&&p->val>q->val){
                preq=q;
                q=q->next;
            }
            
            //插入操作
            ListNode* s=(ListNode*)malloc(sizeof(ListNode));
            s->val=p->val;
            s->next=preq->next;
            preq->next=s;
 
            preq=sortedHead;
            q=preq->next;
        }
        return sortedHead->next;
    }
};

第一次AC代码：

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head==NULL) return NULL;
        ListNode* p=head;
        ListNode* sortedList=(ListNode*)malloc(sizeof(ListNode));
        sortedList->val=p->val;
        sortedList->next=NULL;
        ListNode* q=sortedList;
        ListNode* preq=NULL;
        bool notmove=true;
        while(p->next!=NULL){
            p=p->next;
            while(q!=NULL&&p->val>q->val){
                preq=q;
                q=q->next;
                notmove=false;
            }
            
            ListNode* s=(ListNode*)malloc(sizeof(ListNode));
            if(notmove){
                if(p->val>q->val)
                    {s->val=p->val;q->next=s;s->next=NULL;}//插入尾部
                else 
                    {s->val=p->val;s->next=q;sortedList=s;}//插入头部
            }else{
                if(q==NULL)
                {
                    if(p->val>preq->val)
                       {s->val=p->val;preq->next=s;s->next=NULL;}//插入尾部
                }
                else{s->val=p->val;s->next=preq->next;preq->next=s;}//插入中间
            }
            q=sortedList;
            preq=NULL;
            notmove=true;
        }
        return sortedList;
    }
};