# Real Constant Space! 9 variables total, no recursion

• ``````public ListNode sortList(ListNode head) {

int N = 0;
while (p != null) {
N++;
p = p.next;
}

ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode pre = dummy;
ListNode p2 = p1;
ListNode p3 = p2.next;
int size = 1;
int count = 0;

while (size < N ) {
pre = dummy;
p1 = pre.next;
p2 = p1;
p3 = p2;

while (p1 != null) {
count = size;
while (count != 0 && p2.next != null) {
count--;
p2 = p2.next;
}
if (count > 0) {
pre.next = p1;
break;
}

p3 = p2;
count = size;
while (count != 0 && p3 != null) {
count--;
p3 = p3.next;
}

pre = merge(pre, p1, size, p2, size - count);

if (p3 == null || count != 0)
break;

p1 = p3;
p2 = p1;
}
size *= 2;
}

return dummy.next;
}

public ListNode merge(ListNode pre, ListNode p1, int size1, ListNode p2,
int size2) {
pre.next = p1;
while (size1 != 0 && size2 != 0) {
if (p2.val < p1.val) {
pre.next = p2;
p2 = p2.next;
pre.next.next = p1;
pre = pre.next;
size2--;
} else {
pre = p1;
p1 = p1.next;
size1--;
}
}

if (size2 == 0) {
while (size1 != 0) {
pre = pre.next;
size1--;
}
pre.next = null;
return pre;
}

if (size1 == 0) {
pre.next = p2;
while (size2 != 0) {
pre = pre.next;
size2--;
}
}

return pre;
}``````

• Would be nice if you wrote at least a short overview about how it works.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.