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.