注解

不想太吐槽这个输入测试，这个代码跑不过的，时间不够；但是按照题目要求应该是做好了，这是快排；为了让测试跑得过，把所有函数都写成inline了，即使如此也是不能。

代码

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // * - 异常流处理
        if(head == nullptr){
            return nullptr;
        }
        // 1 - 将链表打平为 vector
        vector<ListNode* > nodeVec;
        flatten(head, nodeVec);
        // 2 - 对 vector 进行快速排序
        fastSort(nodeVec, 0, nodeVec.size()-1);
        // 3 - 重新将 vector 组合为链表
        makeList(nodeVec);
        // 4 - 返回结果
        return nodeVec[0];
    }
private:
    // 将链表打平为 vector
    inline void flatten(ListNode* node, vector<ListNode*>& nodeVec){
        while(node != nullptr){
            nodeVec.push_back(node);
            node = node->next;
        }
    }
    
    // 两个节点的值比较函数
    inline bool compare(ListNode* node1, ListNode* node2, bool flag){
        if(flag){
            return node1->val > node2->val;
        }else{
            return node1->val < node2->val;
        }
    }
    
    inline void swap(ListNode*& node1, ListNode*& node2){
        ListNode* tmp = node1;
        node1 = node2;
        node2 = tmp;
    }
    
    // 快排
    inline void fastSort(vector<ListNode *>& nodeVec, int left, int right){
        // * - 异常流处理
        if(left >= right){
            return;
        }
        // 1 - 确定哨兵，以及左右边界
        int _left = left, _right = right;
        // 2 - 进行快速排序
        while(_left < _right){
            while(compare(nodeVec[left], nodeVec[_right], false)){
                _right--;
            }
            while(compare(nodeVec[left], nodeVec[_left], true)){
                _left++;
            }
            if(_left < _right){
                swap(nodeVec[_left], nodeVec[_right]);
            }
        }
        swap(nodeVec[left], nodeVec[_left]);
        // 3 - 重新确定左右边界
        int left1 = left, right1 = _left-1;
        int left2 = _left+1, right2 = right;
        fastSort(nodeVec, left1, right1);
        fastSort(nodeVec, left2, right2);
    }
    
    // 重新连接链表
    inline void makeList(vector<ListNode* >& nodeVec){
        int loopTime = nodeVec.size()-1;
        for(int i=0; i<loopTime; i++){
            nodeVec[i]->next = nodeVec[i+1];
        }
        nodeVec[loopTime]->next = nullptr;
    }
};