# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:

    def quickSortList(self, head: ListNode):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next: return head
        val = head.val
        left = ListNode(-1); ltail = left
        mid = ListNode(-1); mtail = mid
        right = ListNode(-1); rtail = right

        p = head
        while p:
            if p.val < val:
                ltail.next = p
                ltail = p
            elif p.val == val:
                mtail.next = p
                mtail = p
            else:
                rtail.next = p
                rtail = p
            p = p.next
        ltail.next = None; mtail.next = None; rtail.next = None
        left.next = self.quickSortList(left.next)
        right.next = self.quickSortList(right.next)

        self.get_tail(left).next = mid.next
        self.get_tail(left).next = right.next

        return left.next

    def get_tail(self, head: ListNode) -> ListNode:
        while head.next:
            head = head.next
        return head