class Solution:
    def quickSortList(self, head):
        if not head or not head.next:
            return head #递归返回
        pivot = head.val
        left, mid, right = ListNode(0), ListNode(0), ListNode(0)
        left_tail, mid_tail, right_tail = left, mid, right
        #先整体有序
        while head:
            if head.val < pivot:
                left_tail.next = head
                left_tail = left_tail.next
            elif head.val > pivot:
                right_tail.next = head
                right_tail = right_tail.next
            else:
                mid_tail.next = head
                mid_tail = mid_tail.next
            head = head.next
        left_tail.next = mid_tail.next = right_tail.next = None

        #后部分有序
        left.next = self.quickSortList(left.next)
        right.next = self.quickSortList(right.next)

        # left - mid - right 合并
        self.get_tail(left).next = mid.next  # left.next = None 变成 left.next = 数
        self.get_tail(mid).next = right.next

        return left.next

    def get_tail(self, head):
        while head.next : # 有尾节点的话就:
            head = head.next
        return head