First of all, allow me to explain the meaning of **strict O(1) auxiliary space complexity**.

It means the **maximum** number of memory used by the program, except the memory taken by the input data, doesn't change with the input size.

This indicates that, strictly speaking, any solution that involves recursion can never have a strict O(1) auxiliary space complexity. Because the maximum recursion level depends on the the input size and each recursion call consumes memory on stack, thus the maximum number of memory used depends on the input size.

Secondly, allow me to explain my solution based on merge sort.

Assume the length of list is n, which is unknown at the beginning.

```
level log(n) [ A0, A2, A3, ... , An-2, An-1 ]
...
level 2 [ A0, A1, A2, A3 ], [A4, A5, A6, A7] ,... , [ ..., An-2, An-1 ]
level 1 [ A0, A1], [A2, A3 ], [A4, A5], [A6, A7] ,... , [An-2, An-1]
level 0 [ A0 ], [ A1] , [ A2 ], [ A3 ],... , [ An-2 ], [ An-1 ]
```

At each level, each group only contains at maximum 2^level elements. Merge-sort theses groups pair by pair. Then level ++. Stop until 2^level > n.

Assume the original input is :

```
level 0 5, 3, 6, 1, 4, 2, 7
```

After level 0, we got the length of the list and the list become:

```
level 1 3, 5, 1, 6, 2, 4, 7
```

Now each group contains 2 elements. After level 1, the list become:

```
level 2 1, 3, 5, 6, 2, 4, 7
```

Now each group contains 2^2 = 4 elements. After level 2, the list become:

```
level 3 1, 2, 3, 4, 5, 6, 7
```

Now, 2^3 > 7, stop.

Time complexity:

In each level, each node is visited by at maximum twice. And there are log(n) level. Thus the time complexity is O(2n* log n ) => O( n* log n )

Here is the code:

```
public class Solution {
private class MergeHelper {
public ListNode newHead;
public ListNode newTail;
}
public ListNode sortList(ListNode head) {
if ( head == null || head.next == null) {
return head;
}
ListNode dummyHeadOne = new ListNode(0);
ListNode dummyHeadTwo = new ListNode(0);
ListNode dummySortedHead = new ListNode(0);
ListNode dummySortedLast = dummySortedHead;
ListNode unvisitedNode = head;
MergeHelper mergeRst = new MergeHelper();
int listLength = 0;
int level = 0;
while ( unvisitedNode != null && unvisitedNode.next != null ) {
unvisitedNode = addNode ( dummyHeadOne, unvisitedNode, 1<<level);
unvisitedNode = addNode ( dummyHeadTwo, unvisitedNode, 1<<level);
merge ( dummyHeadOne.next, dummyHeadTwo.next, mergeRst);
dummySortedLast.next = mergeRst.newHead;
dummySortedLast = mergeRst.newTail;
listLength += 2;
}
if (unvisitedNode != null) {
dummySortedLast.next = unvisitedNode;
listLength ++;
}
level ++;
while ( listLength > 1 << level) {
dummySortedLast = dummySortedHead;
unvisitedNode = dummySortedHead.next;
while (unvisitedNode != null) {
unvisitedNode = addNode ( dummyHeadOne, unvisitedNode, 1<<level);
unvisitedNode = addNode ( dummyHeadTwo, unvisitedNode, 1<<level);
merge ( dummyHeadOne.next, dummyHeadTwo.next, mergeRst);
dummySortedLast.next = mergeRst.newHead;
dummySortedLast = mergeRst.newTail;
}
level ++;
}
return dummySortedHead.next;
}
/* merge listOne and listTwo.
Save the sorted list head into rst.newHead
Save the last node of the sorted list into rst.newTail
*/
private void merge (ListNode listOne, ListNode listTwo, MergeHelper rst) {
ListNode dummyHead = new ListNode (0);
ListNode lastNode = dummyHead;
while (listOne != null && listTwo != null) {
if ( listOne.val < listTwo.val ) {
lastNode.next = listOne;
listOne = listOne.next;
} else {
lastNode.next = listTwo;
listTwo = listTwo.next;
}
lastNode = lastNode.next;
}
while (listOne != null) {
lastNode.next = listOne;
listOne = listOne.next;
lastNode = lastNode.next;
}
while ( listTwo != null ) {
lastNode.next = listTwo;
listTwo = listTwo.next;
lastNode = lastNode.next;
}
rst.newHead = dummyHead.next;
rst.newTail = lastNode;
}
/*
add at max #"count" nodes into "head" from "source"
return the new position of source after adding.
*/
private ListNode addNode ( ListNode head, ListNode source, int count ) {
while (count > 0 && source != null) {
head.next = source;
head = head.next;
source = source.next;
count --;
}
head.next = null;
return source;
}}
```

Space complexity:

There are no recursion calls in this solution. Thus the maximum number of function calls is constant.

The number of dummy nodes is constant.

Thus the auxiliary space complexity is O(1).