Relatively short Iterative Mergesort Java Solution


  • 1
    S
        /*
        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 {
        public ListNode sortList(ListNode head) {
            ListNode dummy=new ListNode(0);
            dummy.next=head;
            int length=0;
            for(ListNode current=head; current!=null; current=current.next)
                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;
        }
    }

Log in to reply
 

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