/** * 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)     {        //链表不能从后往前扫描，所以每次从头往后扫描？        //有没有更好的解决方案，细节的提升,        ListNode *cur;        ListNode *pre;        if(head == NULL)            return NULL;        if(head->next == NULL)            return head;        pre = head;        cur = head->next;        while(cur != NULL)        {            //scan from the head            if(cur->val < pre->val)            {                ListNode *innercur = head->next;                ListNode *innerpre = head;                while(cur->val > innercur->val)                {                    innercur = innercur->next;                    innerpre = innerpre->next;                }                if(innerpre == head && innerpre->val > cur->val)                {                    pre->next = cur->next;                    cur->next = head;                    head = cur;                }                else                {                    pre->next = cur->next;                    innerpre->next = cur;                    cur->next = innercur;                }                cur = pre->next;            }            else            {                pre = pre->next;                cur = cur->next;            }        }        return head;    }};

/** * 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) {        //insertion sort mean that element before i must be sorted        ListNode *newhead = new ListNode(INT_MIN);        newhead->next = head;        ListNode *spre = newhead;        ListNode *scur = head;        //change scur!!!        while(scur != NULL) {            ListNode *pre = newhead;            ListNode *cur = newhead->next;            while(cur != scur && cur->val <= scur->val) {                pre = pre->next;                cur = cur->next;            }            //change            if(cur != scur) {                spre->next = scur->next;                pre->next = scur;                scur->next = cur;                                scur = spre->next;            }            else {                spre = spre->next;                scur = scur->next;            }        }        ListNode *ans = newhead->next;        delete newhead;        return ans;    }};