I have implemented the quick sort version, time complexity O(NlogN), space O(1).

```
def sortList(self, head: ListNode, untilNone):
"""
:type head: ListNode
:rtype: ListNode
"""
def sort(head, until=None):
'''
Sort the list from head until `until`.
'''
if head == until:
return head
dummy = ListNode(None)
dummy.next = head
pivot = head.val
smaller = dummy
equal = dummy.next
while equal.next not in (None, until) and equal.next.val == equal.val:
equal = equal.next
prev = equal
p = prev.next
while p not in (None, until):
if p.val < pivot:
prev.next = p.next
p.next = smaller.next
smaller.next = p
smaller = p
elif p.val == pivot and equal.next != p:
prev.next = p.next
p.next = equal.next
equal.next = p
equal = p
else:
prev = p
p = prev.next
dummy.next = sort(dummy.next, smaller.next)
equal.next = sort(equal.next, until)
return dummy.next
return sort(head)
```