/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    int temp=0;
    ListNode* getPartition(ListNode* pBegin, ListNode* pEnd){
        int key = pBegin->val;
        ListNode* left = pBegin;
        ListNode* right = pBegin->next;
        while(right != pEnd){
            if(right->val < key){
                left = left->next;
                this->temp = right->val;
                right->val = left->val;
                left->val = this->temp;
            }
            right = right->next;
        }

        this->temp = left->val;
        left->val = pBegin->val;
        pBegin->val = this->temp;

        return left;

    }
    
    void quick_sort(ListNode* pBegin, ListNode*pEnd){
        if(pBegin != pEnd){
            ListNode* partition = getPartition(pBegin, pEnd);
            quick_sort(pBegin, partition);
            quick_sort(partition->next, pEnd);
        }
    }
    
    ListNode* sortList(ListNode* head) {
        quick_sort(head, nullptr);
        return head;
    }
};

leetcode148 C++ 340ms 单链表快速排序 两个指针均为left->right移动