/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* get_tail(ListNode* head) {
        while (head->next) head = head->next;
        return head;
    }
    ListNode* quickSortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* l = new ListNode(0);
        ListNode* mid = new ListNode(0);
        ListNode* r = new ListNode(0);
        int val = head->val;
        ListNode* cl = l;
        ListNode* cmid = mid;
        ListNode* cr = r;
        while (head) {
            if (head->val > val) {
                cr->next = head;
                cr = cr->next;
            }else if (head->val == val) {
                cmid->next = head;
                cmid = cmid->next;
            }else{
                cl->next = head;
                cl = cl->next;
            }
            head = head->next;
        }
        cr->next = cmid->next = cl->next = nullptr;
        l->next = quickSortList(l->next);
        r->next = quickSortList(r->next);

        get_tail(l)->next = mid->next;
        get_tail(mid)->next = r->next;
        return l->next;
    }
};