Share my java merge sort solution.


  • 1
    H

    Some codes may be not elegant, welcome improvement!

    public static ListNode sortList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode end = head;
            while(end .next != null){
                end = end.next;
            }
            return sort(head, end);
        }
        public static ListNode sort(ListNode start, ListNode end){
            if(start.next == end){
                if(start.val > end.val){
                    end.next = start;
                    start.next = null;
                    return end;
                }
            }
            if(start == end){
            	start.next = null;
            	return start;   	
            }
            ListNode middle = middle(start, end);
            ListNode middleNext = middle.next;
            ListNode left = sort(start, middle);
            ListNode right = sort(middleNext, end);
            
            ListNode dummy = new ListNode(-1);
            ListNode head = dummy;
            while(left != null && right != null){
                if(left.val < right.val){
                    head.next = left;
                    left = left.next;
                }else{
                    head.next = right;
                    right = right.next;
                }
                head = head.next;
            }
            head.next = left == null ? right : left;
            return dummy.next;
        }
        public static ListNode middle(ListNode start, ListNode end){
            ListNode slow = start;
            ListNode fast = start;
            while(fast != end && fast.next != end){
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

Log in to reply
 

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