题解 | #万万没想到之聪明的编辑#

利用快排思想，把头节点作为标记，采取值交换的方式将比标记小或大的分别放在两边

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* Get_Partion(ListNode* B, ListNode* E){
        if(B==nullptr||B->next==E) return B;
        int key=B->val;
        ListNode *p=B,*q=p->next;
        while(q!=E){
            if(q->val<key){
                p=p->next;
                swap(p->val,q->val);
            }
            q=q->next;
        }
        swap(p->val,B->val);
        return p;
    }
    void QuickSort(ListNode* B, ListNode* E){
        if(B==E) return;
        ListNode *P = Get_Partion(B, E);
        QuickSort(B, P);
        QuickSort(P->next, E);
    }

    ListNode* sortInList(ListNode* head) {
        QuickSort(head,nullptr);
        return head;
    }

};