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): def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ def mysort(head): """ :type head: 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 mid = head s_head = None 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 s_head = copy(i.next) s_tail = s_head 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) mid.next = new_head_bigger # Step 3: Get the smaller part sorted last_diff_node = None n = s_head 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 new_head_smaller, new_end_smaller = mysort(s_head) else: new_head_smaller, new_end_smaller = s_head, s_tail mid_start = mid # Step 4, join. # There is only bigger list if not new_head_smaller and new_head_bigger: return mid_start, new_end_bigger # There is only a smaller list if not new_head_bigger and new_head_smaller: new_end_smaller.next = mid_start return new_head_smaller, mid # There are both bigger and smaller lists if new_head_smaller and new_head_bigger: new_end_smaller.next = mid_start mid.next = new_head_bigger # Concatenate two list and return return new_head_smaller, new_end_bigger return mysort(head)