I solved the problem in Java with recursion, merge sort. But I realized that it don't have a **constant space complexity**.

Every time the function is used, constant space is allocated. The function will be used nearly log(n) times, so the space complexity is log(n).

Maybe it can only be solved without recursion while it has a constant space complexity.

Anyone agrees with me? Who solve it **without recursion**?

Even though it's not necessary, here is my **accepted** code: (2 ints and 3 pointers of ListNode are allocated when the funtion is used every time.)

```
public class Solution {
public ListNode sortList(ListNode head) {
int len = 0;
for( ListNode now=head; now!=null; now=now.next )
++len;
if(len<2)
return head;
ListNode firstHead, secondHead, tail;
firstHead = tail = secondHead = head;
for( int pos=0; pos+1<len/2; ++pos )
tail = tail.next; //"tail" is the firstHead's tail
secondHead = tail.next;
tail.next = null;
firstHead = sortList(firstHead);
secondHead = sortList(secondHead);
tail=null; //"tail" is the tail of new sorted list now
while( firstHead!=null&&secondHead!=null )
{
if(tail==null)
{
if(firstHead.val<=secondHead.val)
{
tail = head = firstHead; //"head" becomes the head of new sorted list
firstHead = firstHead.next;
}
else
{
tail = head = secondHead;
secondHead = secondHead.next;
}
}
else
{
if(firstHead.val<=secondHead.val)
{
tail.next = firstHead;
firstHead = firstHead.next;
}
else
{
tail.next = secondHead;
secondHead = secondHead.next;
}
tail = tail.next;
}
}
if( firstHead==null )
tail.next = secondHead;
else if( secondHead==null )
tail.next = firstHead;
return head;
}
}
```