```
public ListNode sortList(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
int n = 0, lCnter, rCnter;
while (head != null) { head = head.next; n++;}
ListNode cur, tail = null; //cur is always previous node of head of each sub-merged list
ListNode l, r;
for (int mergeN = 2; mergeN / 2 <= n; mergeN *= 2) {
cur = dummyHead;
for (int subN = 0; subN < n; subN += mergeN) {
l = cur.next; r = l;
for (int k = 0; k < mergeN / 2; k++) {
r = r.next;
if (r == null) break;
}
if (r == null) break; //other half of is empty, no need to sort
//merge l list and r list with mergeN elements
lCnter = 0; rCnter = 0;
if (l.val < r.val) {
cur.next = l;
l = l.next;
lCnter++;
} else {
cur.next = r;
r = r.next;
rCnter++;
}
for (int k = 1; true; k++) {
cur = cur.next;
if (lCnter == mergeN / 2 && (rCnter == mergeN / 2 || r == null)) break;
if (lCnter == mergeN / 2) {
cur.next = r;
tail = r;
r = r.next;
rCnter++;
continue;
}
if (rCnter == mergeN / 2 || r == null) {
cur.next = l;
tail = l;
l = l.next;
lCnter++;
continue;
}
if (l.val < r.val) {
cur.next = l;
l = l.next;
lCnter++;
} else {
cur.next = r;
r = r.next;
rCnter++;
}
}
cur.next = r;
}
}
return dummyHead.next;
}
```