/
* 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;
    auto left_head = new ListNode(-1);
    auto right_head = new ListNode(-1);
    auto mid_head = new ListNode(-1);

    // ！！！！ 必须要建立一个mid链表 否者会出现首个元素比后面的都大（小），
    // 导致链表并没有划分，这样循环递归，一直不会退出。
    auto ltail = left_head, mtail = mid_head,rtail = right_head; 
    int val = head -> val;

    for (auto p = head; p; p = p -> next) {
        if (p -> val < val) ltail = ltail -> next = p;
        else if (p -> val == val) mtail = mtail -> next = p; 
        else rtail = rtail -> next = p;
    }

    ltail -> next = mtail -> next = rtail -> next = nullptr;
    left_head -> next = quickSortList(left_head -> next);
    right_head -> next = quickSortList(right_head -> next);

    get_tail(left_head) -> next = mid_head -> next;
    get_tail(left_head) -> next = right_head -> next;
    auto result = left_head -> next;
    delete left_head;
    delete mid_head;
    delete right_head;
    return result;
}

};