/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode quickSortList(ListNode head) {

        if (head == null || head.next == null){
            return head;
        }

        // 声明左、中、右三个链表
        ListNode left = new ListNode(-1);
        ListNode right = new ListNode(-1);
        ListNode mid = new ListNode(-1);
        //快排每次选择第一个节点的值作为对比
        int v = head.val;
        while (head != null){
            ListNode temp = head.next;
            //将小于v的值加入到left链表中
            if (head.val < v){
                head.next = left.next;
                left.next = head;
            //将大于v的值加入到right链表中
            }else if (head.val > v){
                head.next = right.next;
                right.next = head;
            //将等于v的值加入到mid链表中
            }else{
                head.next = mid.next;
                mid.next = head;
            }
            head = temp;
        }
        //递归排序做链表和右链表
        left.next = quickSortList(left.next);
        right.next = quickSortList(right.next);
        //找到左链表的尾节点，令其指向中链表
        ListNode t = left;
        while (t.next != null){
            t = t.next;
        }
        t.next = mid.next;
        //再找到中链表的尾节点，令其指向右链表
        while (t.next != null){
            t = t.next;
        }
        t.next = right.next;
        return left.next;
    }
}