# Merge-sort with detailed explanation. Java, O(1) space, O(nlogn) time

• Just like merge-sort in an array, what we should do is to merge-sort the list.
Take `[3->1->2->5->6->4->3]->null` for example.
We just find the middle point (5), and cut it to two lists `[3->1->2->5]->6` and `[6->4->3]->null`.
Here 6 in the first list meas the next ListNode. Then we need to merge `[3->1->2->5]` with next 6.

In order to merge sort, we just need to compare the two sublists. Each time, choose the smaller one in the list. Remember, do not use any extra memory during merge!

Here is a sample.

``````(1) [3->1->2->5->6->4->3]->null
(2) [3->1->2->5]->6, [6->4->3]->null // split (1)
(3) [3->1]->2, [2->5]->6 // split (2.1)
(4) [3]->1, [1]->2 // split (3.1)
(5) [1->3]->2 // merge (4)
(6) [2]->5, [5]->6 // split (3.2)
(7) [2->5]->6 // merge (5)
(8) [1->2->3->5]->6 // merge (5) and (7)
(9) [6->4]->3, [3]->null // split (2.2)
(10) [6]->4, [4]->3 // split (9.1)
(11) [4->6]->3 // merge (10)
(12) [3->4->6]->null // merge (10) and (9.2)
(13) [1->2->3->3->4->5->6]->null // merge (8) and (12)
``````

So, we can remember after in order to reform the list.

Here is the code with comments.

``````public class Solution {
while (end.next!=null) end=end.next; // find the end point
}
// sort from head to end. 'after' is the next point of this sub-list.
private ListNode sortList(ListNode head, ListNode end, ListNode after) {
p.next=sortList(p.next, end, after);
}
// find the middle point in order to split the list
private ListNode findMiddlePoint(ListNode head, ListNode after) {
while (q.next!=after && q.next.next!=after) {
p=p.next;
q=q.next.next;
}
return p;
}
// merge the two array. Remember: the after of l1 is l2.
private ListNode merge(ListNode l1, ListNode l2, ListNode after) {
ListNode p=l1, q=l2;
while (p!=l2 || q!=after) {
if (p==l2) {
if (w==null) {
w=q;
}
else {
w.next=q;
w=w.next;
}
q=q.next;
continue;
}
if (q==after) {
if (w==null) {
w=p;
}
else {
w.next=p;
w=w.next;
}
p=p.next;
continue;
}
if (p.val<q.val) {
if (w==null) {
w=p;
}
else {
w.next=p;
w=w.next;
}
p=p.next;
}
else {
if (w==null) {
w=q;
}
else {
w.next=q;
w=w.next;
}
q=q.next;
}
}
w.next=after;