ACM-单向链表插入排序算法（在原链表上操作）

链接：https://www.nowcoder.com/questionTerminal/152bc6c5b14149e49bf5d8c46f53152b?toCommentId=1610886
来源：牛客网

/*
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;
    }
};