链表的插入排序【C++】

把链表分为两部分，一部分是已经排序的链表，另一部分是还未排序的链表。每次把未排序的链表的头节点插入到已排序链表中，直到未排序链表为空为止。
时间复杂度O(n^2)，空间复杂度O(1)。

ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* temp_head = new ListNode(-1);    //新增一个节点插在头节点前
    temp_head->next = head;
    ListNode* pNode = head->next;    //当前要排序的节点
    head->next = nullptr;            //断开head节点与后面节点的连接，把链表分为两部分，分别以temp_head和pNode为头节点
    while (pNode) {
        //在已排序链表中寻找插入位置
        ListNode* pTemp = temp_head->next;    //pTemp指向已排序部分的第一个节点
        ListNode* pPreTemp = temp_head;    //pPreTemp是pTemp的前一个节点
        while (pTemp && pTemp->val <= pNode->val) {
            pTemp = pTemp->next;
            pPreTemp = pPreTemp->next;
        }        //循环结束时pTemp是已排序链表中第一个大于pNode的节点

        //在把pNode插入到pTemp前之前，需要先断开pNode与其他节点的连接
        ListNode* pNext = pNode->next;
        pNode->next = nullptr;

        //把pNode插入到pPreTemp 和pTemp之间
        pPreTemp->next = pNode;
        pNode->next = pTemp;

        pNode = pNext;    //pNode右移
    }
    return temp_head->next;
}