题解 | #单链表的排序# 快速排序c++写法 超99%时间

快速排序c++写法超99%时间写法

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* solve(ListNode* head, ListNode* pend){
        if(head==NULL||head->next==pend) return head;
        int val = head->val;
        ListNode* p = head;
        ListNode* q = p->next;
        while(q!=pend){
            if(q->val < val){
                p = p->next;
                swap(p->val, q->val);
            }
            q = q->next;
        }
        swap(head->val, p->val);
        return p;
    }

    void quick_sort(ListNode* head, ListNode* pend){
        if(head==pend) return;
        ListNode* p = solve(head, pend);
        quick_sort(head, p);
        quick_sort(p->next, pend);
    }

    ListNode* sortInList(ListNode* head) {
        // write code here
        quick_sort(head, NULL);
        return head;
    }
};