Relatively short Iterative Mergesort Java Solution

• ``````    /*
A small trick used in the following code is that, in order to sort the following sublist of length 4, e.g.
Start -> 5 -> 6 -> 2 -> 8 ->Tail (assume list is already sorted under length 2)
I break the sublist into 3 parts:
1) Start -> Tail
2) 5 -> 6 -> Null
3) 2 -> 8 -> Null
And then try to insert nodes from sublists 2) and 3) into 1).
*/

public class Solution {
ListNode dummy=new ListNode(0);
int length=0;
length++;
for(int len=2;len/2<=length; len*=2){
ListNode start=dummy, mid=dummy, end=dummy;
while(start.next!=null){
for(int i=0;i<len/2;i++){
mid= mid.next==null? mid:mid.next;
if(end.next==null)
continue;
end= end.next.next==null? end.next:end.next.next;
}
ListNode left=start.next, right=mid.next, next=end.next;
start.next=next;
mid.next=null;
end.next=null;
while(left!=null||right!=null){
if(right==null||left!=null&&right!=null&&left.val<right.val){
ListNode temp=left.next;
left.next=start.next;
start.next=left;
left=temp;
}
else if(left==null||left!=null&&right!=null&&left.val>=right.val){
ListNode temp=right.next;
right.next=start.next;
start.next=right;
right=temp;
}
start=start.next;
}
mid=start;
end=start;
}
}
return dummy.next;
}
}``````

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