# Python O(1) space and O(nlogn) time solution(but slow, please advice)

• The difficulty of this one is O(1) space, my idea is to apply quick sort algorithm as follows, and code is in the answer part.

1 Given a list, chose the first element to be the pivotal value.

2 Scan through the list, take out every element equal to or smaller than pivotal value to form a second list called "smaller"

3 (important, otherwise TLE) check the smaller list, if at the end there are several nodes that has the same value as standard value, shrink the smaller list to exclude those nodes. By the end of this step, you got 3 part, smaller list, pivotal, bigger list.

4 Apply the smaller list and bigger list to the function recursively.

5 Join these three parts together to form a sorted list.

• `````` class Solution(object):
"""
:rtype: ListNode
"""
"""
:rtype: (ListNode head, ListNode tail)
"""
if not head: # Len = 0
return None, None
if not head.next: # len = 1
return (head, head) #  Length 0 or 1
# Step 1, use the first node to devide the whole list into 3 parts. Smaller, mid, bigger
s_tail = None
i = mid
while i and i.next:
if i.next.val <= mid.val:
# Take a copy of this node to the smaller list.
if not s_head: #  Find the first smaller node
else:
s_tail.next = copy(i.next)
s_tail = s_tail.next
#  Then delete the smaller node from main list
i.next = i.next.next
else:
i = i.next
if s_tail:
s_tail.next = mid

#  Step 2: Get the bigger part sorted.
new_head_bigger, new_end_bigger = mysort(mid.next)
#  Step 3: Get the smaller part sorted
last_diff_node = None
while n and n is not mid:
if n.val < mid.val:
last_diff_node = n
n = n.next
if last_diff_node:
mid_start = last_diff_node.next
last_diff_node.next = None
else:
mid_start = mid
# Step 4, join.
#  There is only bigger list
return mid_start, new_end_bigger

# There is only a smaller list