The ticky is dividing the list into three part in every scan loop. Left part is less than pivot, middle part is equals to pivot, and right part is greater than pivot.

```
# requirement: hat is not None
def quick_sort(hat, tail):
if hat.next is tail or hat.next.next is tail:
return
hat1, hat2, hat3 = hat, hat.next, ListNode(None)
tail1, tail2, tail3 = hat1, hat2, hat3
p, pivot = hat2.next, hat2.val
while p is not tail:
if p.val < pivot:
tail1.next, tail1, p = p, p, p.next
elif p.val == pivot:
tail2.next, tail2, p = p, p, p.next
else:
tail3.next, tail3, p = p, p, p.next
# Caution: DO NOT change the order of these three line codes below.
tail3.next = tail
tail2.next = hat3.next
tail1.next = hat2
quick_sort(hat1, hat2)
quick_sort(tail2, tail)
class Solution:
# @param {ListNode} head
# @return {ListNode}
def sortList(self, head):
hat = ListNode(None)
hat.next = head
quick_sort(hat, None)
return hat.next
```