```
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
int size = 0;
ListNode fakehead = new ListNode(-1);
fakehead.next = head;
for (ListNode len = head; len!= null; len = len.next)
size ++;
for (int length = 1; length < size; length *= 2)
{
ListNode firstBegin = fakehead.next;
ListNode secondBegin = fakehead.next;
ListNode temp = fakehead;
for (int begin = 0 ; begin < size; begin += 2 * length)
{
int valid = size - begin;
int leftcounter = Math.min(length, valid);
int rightcounter = Math.min(length, valid - leftcounter);
for (int i = 0; i < leftcounter; i++)
secondBegin = secondBegin.next;
while (leftcounter > 0 && rightcounter > 0)
{
if (firstBegin.val > secondBegin.val)
{
temp.next = secondBegin;
secondBegin = secondBegin.next;
rightcounter--;
}
else
{
temp.next = firstBegin;
firstBegin = firstBegin.next;
leftcounter--;
}
temp = temp.next;
}
while (leftcounter > 0)
{
temp.next = firstBegin;
firstBegin = firstBegin.next;
leftcounter--;
temp = temp.next;
}
while (rightcounter > 0)
{
temp.next = secondBegin;
secondBegin = secondBegin.next;
rightcounter--;
temp = temp.next;
}
temp.next = firstBegin = secondBegin;
}
}
return fakehead.next;
}
```