C++ 解法, 执行用时: 8ms, 内存消耗: 1656KB, 提交时间: 2021-09-08

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        vector<int> tmp;
        ListNode* cur = head;
        while(cur){
            tmp.push_back(cur->val);
            cur = cur->next;
        }
        sort(tmp.begin(), tmp.end());
        int i = 0;
        cur = head;
        while(cur){
            cur->val = tmp[i];
            i++;
            cur = cur->next;
        }
        delete cur;
        return head;
    }
};

C++ 解法, 执行用时: 8ms, 内存消耗: 1676KB, 提交时间: 2021-09-14

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) 
    {
        // write code here
        vector<int>iv;
        ListNode* tmp;
        tmp = head;
        while(tmp)
        {
            iv.push_back(tmp->val);
            tmp = tmp->next;
        }
        sort(iv.begin(),iv.end());
        tmp = head;
        int i = 0;
        while(tmp)
        {
            tmp->val = iv[i];
            tmp = tmp->next;
            i++;
        }
        return head;
    }
};

C++ 解法, 执行用时: 9ms, 内存消耗: 1556KB, 提交时间: 2021-09-07

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

// class Solution {
// public:
//     /**
//      * 
//      * @param head ListNode类 the head node
//      * @return ListNode类
//      */
//     ListNode* sortInList(ListNode* head) {
//         // write code here
//         int count  = 0;
//         ListNode* p = head;
//         while(p != NULL){
//             count++;
//             p = p->next;
//         }
//         ListNode** arr = (ListNode**)malloc(sizeof(ListNode*)*count);
//         int i = 0;
//         p = head;
//         while(p != NULL){
//             arr[i] = p;
//             p = p->next;
//             i++;
//         }
//         for(int j = 0;j < count - 1;j++){
//             for(int k=0;k < count - j - 1;k++){
//                 if(arr[k]->val > arr[k+1]->val){
//                     ListNode* tmp = arr[k];
//                     arr[k] = arr[k+1];
//                     arr[k+1] = tmp;
//                 }
//             }
//         }
//         ListNode* result;
//         ListNode* cursor;
//         result = arr[0];
//         cursor = result;
//         i = 1;
//         while(i < count){
//             cursor->next = arr[i];
//             cursor = cursor->next;
//             i++;
//         }
//         return result;
//     }
// };
class Solution {
public:
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr)
            return nullptr;
        quick_sort(head,nullptr);
        return head;
    }
     
    void quick_sort(ListNode *start,ListNode *end){
        if(start != end && start->next != end){
            ListNode *mid = findAndSort(start,end);
            quick_sort(start, mid);
            quick_sort(mid->next, end);
        }
        //return start;
    }
     
    ListNode *findAndSort(ListNode *start,ListNode *end){
        ListNode *p = start;
        ListNode *q = p->next;
        int val = start->val;
        while(q != end){
            if(q->val < val){
                p = p->next;
                swap(p->val,q->val);
            }
            q = q->next;
        }
        swap(p->val,start->val);
        return p;
    }
};

C++ 解法, 执行用时: 9ms, 内存消耗: 1556KB, 提交时间: 2021-08-09

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr)
            return nullptr;
        quick_sort(head,nullptr);
        return head;
    }
    
    void quick_sort(ListNode *start,ListNode *end){
        if(start != end && start->next != end){
            ListNode *mid = findAndSort(start,end);
            quick_sort(start, mid);
            quick_sort(mid->next, end);
        }
        //return start;
    }
    
    ListNode *findAndSort(ListNode *start,ListNode *end){
        ListNode *p = start;
        ListNode *q = p->next;
        int val = start->val;
        while(q != end){
            if(q->val < val){
                p = p->next;
                swap(p->val,q->val);
            }
            q = q->next;
        }
        swap(p->val,start->val);
        return p;
    }
};



// if(head == nullptr)
//             return nullptr;
//         ListNode *cur = head;
//         vector<int> res;
//         while(cur){
//             res.push_back(cur->val);
//             cur = cur->next;
//         }
//         sort(res.begin(),res.end());
//         ListNode *p = head;
//         int k = 0;
//         while(p){
//             p->val = res[k];
//             k++;
//             p = p->next;
//         }
//         return head;

C++ 解法, 执行用时: 9ms, 内存消耗: 1576KB, 提交时间: 2021-09-18

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        vector<int> arr;
        ListNode* newHead = head;
        while(newHead != nullptr){
            arr.push_back(newHead -> val);
            newHead = newHead -> next;
        }
        sort(arr.begin(), arr.end());
        newHead = head;
        for(int i = 0; i < arr.size(); i++){
            newHead -> val = arr[i];
            newHead = newHead -> next;
        }
        return head;
    }
};