class Solution {
public:

// 1. getTail API
ListNode* getTail(ListNode *head){
    while(head->next){
        head = head->next;
    }
    return head;
}


ListNode* quickSortList(ListNode* head) {

    // 2. 空节点或单节点
    if(!head || !head->next) return head;


    // 3. 单链表表头为helper
    ListNode *lhead = new ListNode(-1), *mhead = new ListNode(-1), *rhead = new ListNode(-1);
    auto left = lhead, mid = mhead, right = rhead;

    // 4.遍历链表
    int x = head->val;
    for(auto p = head; p ; p = p->next){
        if (p->val < x)
            left = left->next = p; // 5. 插入元素 + 移动指针
        else if (p->val == x)
            mid = mid->next = p;
        else
            right = right->next = p;
    }

    // 得到三个链表，递归左边和右边链表
    left->next = mid->next = right->next = nullptr; // 6.各个链表尾部置null

    //7. 只需遍历左区间 与 右区间
    lhead->next = quickSortList(lhead->next);
    rhead->next = quickSortList(rhead->next);

    //8. 链表拼接
    getTail(lhead)->next = mhead->next;
    getTail(mhead)->next = rhead->next;


    // 9. 专门的re
    auto re = lhead->next;

    // 10. 内存回收
    delete lhead;
    delete mhead;
    delete rhead;

    return re;
}

};