C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-01-14

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        if(!head || !head->next)
            return head;
        ListNode* cur = head;
        vector<int> res;
        while(cur)
        {
            res.push_back(cur->val);
            cur = cur->next;
        }
        sort(res.begin(),res.end());
        cur = head;
        int index = 0;
        while(cur)
        {
            cur->val = res[index++];
            cur = cur->next;
        }

        return head;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-08

class Solution {
  public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode* c = head;
        vector<int> res;
        while (c) {
            res.push_back(c->val);
            c = c->next;
        }
        sort(res.begin(), res.end());
        c = head;
        int index = 0;
        while (c) {
            c->val = res[index++];
            c = c->next;
        }
        return head;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-01-22

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        if(head==NULL){
            return NULL;
        }else if(head->next == NULL){
            return head;
        }
        
        ListNode* cur = head->next;
        ListNode* pre = head;
        
        ListNode *aux = new ListNode(-1);
        aux->next = head;
        
        while(cur != NULL){
            if(cur->val<pre->val){
                pre->next = cur->next;
                ListNode* l1 = aux;
                ListNode* l2 = aux->next;
                while(cur->val>l2->val){
                    l1=l2;
                    l2=l2->next;
                }
                l1->next = cur;
                cur->next = l2;
                cur = pre->next;
            }else{
                pre = cur;
                cur = cur->next;
              }
        }
        return aux->next;  //返回原单链表的首节点。
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-06-05

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        if (!head || head->next == nullptr)
            return head;

        ListNode* pre_head = new ListNode(-1);
        pre_head->next = head;
        ListNode* search = pre_head;
        ListNode* cur = head->next;
        ListNode* pre = head;

        while (cur)
        {
            if (cur->val < pre->val)
            {
                while (search->next != nullptr && search->next->val < cur->val)
                    search = search->next;

                pre->next = cur->next;
                cur->next = search->next;
                search->next = cur;

                cur = pre->next;
                search = pre_head;
            }
            else
            {
                pre = cur;
                cur = cur->next;
            }
        }
        return pre_head->next;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-02-20

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
//         vector<int> temp;
//         ListNode* p=head;
//         while(p){
//             temp.push_back(p->val);
//             p=p->next;
//         }
//         sort(temp.begin(),temp.end());
//         p=head;
//         for(int i=0;i<temp.size();i++){
//             p->val=temp[i];
//             p=p->next;
//         }
//         return head;
        if(!head||!head->next)return head;
        ListNode* pre=head;
        ListNode* cur=head->next;
        ListNode* dummyhead=new ListNode(-1);
        dummyhead->next=head;
        while(cur){
            if(cur->val<pre->val){
                ListNode* temp=dummyhead;
                while(temp->next->val<cur->val)temp=temp->next;
                pre->next=cur->next;
                cur->next=temp->next;
                temp->next=cur;
                cur=pre->next;
            }
            else{
                cur=cur->next;
                pre=pre->next;
            }
        }
        return dummyhead->next;
    }
};