Java Merge Sort


  • 0
    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            
            ListNode fast = head, slow = head;
            while(fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            
            ListNode h2 = slow.next;
            slow.next = null;
            
            ListNode h1 = sortList(head);
            h2 = sortList(h2);
            
            return merge(h1, h2);
        }
        
        public ListNode merge(ListNode h1, ListNode h2){
            ListNode fakeHead = new ListNode(9);
            ListNode pre = fakeHead;
            while(h1!=null && h2!=null){
                ListNode cur = null;
                if(h1.val<h2.val){
                    cur = h1;
                    h1 = h1.next;
                }else{
                    cur = h2;
                    h2 = h2.next;
                }
                pre.next = cur;
                pre = pre.next;
            }
            
            pre.next = h1!=null ? h1: h2;
            return fakeHead.next;
        }
    }
    

Log in to reply
 

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