/*

1.若链表只有一个节点或者为空，直接返回

2.将链表的前两个节点排序，并将排序之后的第二个节点的下一个节点赋空

3.此时整个链表分为了两个，将未排序的节点一一插入到已排序链表中：

  3.1.第一种情况，待插入节点比排序链表的头节点小

  3.2.第二种情况，待插入节点比排序链表的最后节点大

  3.3.第三种情况，待插入节点可插入到排序链表中

*/

 

class Solution {

public:

    ListNode *insertionSortList(ListNode *head) {

        //输入为空或者只有一个节点

        if(!head || !head->next)return head;

        ListNode *unSortCur = head->next->next;

        if(head->val > head->next->val)

        {

            ListNode *p = head;

            head = head->next;

            head->next = p;

            p->next = nullptr;

        }

        else

            head->next->next = nullptr;

        while(unSortCur != nullptr) //QQQ

        {

            ListNode *sortPre = head;

            ListNode *sortCur = sortPre->next;

            ListNode *unSortNext = unSortCur->next;

            if(unSortCur->val < head->val)

            {

                unSortCur->next = head;

                head = unSortCur;

            }

            else{

                while(sortCur != nullptr && unSortCur->val > sortCur->val)

                {

                    sortCur = sortCur->next;

                    sortPre = sortPre->next;

                }

                if(sortCur == nullptr){

                    sortPre->next = unSortCur;

                    unSortCur->next = nullptr;

                }

                else{

                    sortPre->next = unSortCur;

                    unSortCur->next = sortCur;

                }

            }

            unSortCur = unSortNext;

        }

        return head;

    }

};