# Very modular Java O(1) space solution

• `mergeByK` takes two chunks and merges them with the `merge` function. In the `merge` function, `h`, `h2` and `h3` stand for the head of chunk 1, chunk 2 and the rest.

``````public class Solution {
public ListNode sortList(ListNode head) {
int k=1;
ListNode dummy = new ListNode(0);
int round;
do {
round=0;
ListNode prev = dummy;
do {
prev = mergeByK(prev, prev.next, k);
round ++;
} while (prev.next!=null);
k*=2;
} while (round>1);
return dummy.next;
}

ListNode mergeByK(ListNode prev, ListNode h, int k) {
ListNode h2 = h; int count = k;
while (h2!=null && count>0) {
h2=h2.next; count--;
}
ListNode h3=h2;count=k;
while (h3!=null && count>0) {
h3=h3.next; count--;
}
ListNode[] ret = merge(h, h2, h3);
prev.next = ret[0];
return ret[1];
}

ListNode[] merge(ListNode h, ListNode h2, ListNode h3) {
ListNode dummy=new ListNode(0);
ListNode prev = dummy;
ListNode h2c = h2;
while (h!=h2c || h2!=h3) {
if (h != h2c && (h2 == null || h2 == h3 || h.val < h2.val)) {
prev.next = h; h=h.next;
} else {
prev.next = h2; h2=h2.next;
}
prev = prev.next;
}
prev.next = h3;
return new ListNode[]{dummy.next, prev};
}
}``````

• Did you get AC with this code?

In merge function, you always return null as ret[0].

• Yes, the code gets AC. dummy is used as a hook to get the head of merged list, so ret[0] is not necessarily null.

• you're right, you set the dummy.next via prev.next (and before prev = dummy)

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