Simple Java merge sort with explanation


  • 0
    L
    public class Solution {
    
        public ListNode sortList(ListNode head) {
            if(head == null || head.next==null) {
                return head;
            }
            
            //get the mid.
            ListNode s=head,f=head,prev=head;
            while(f!=null && f.next!=null) {
                prev = s;
                s = s.next;
                f = f.next.next;
            }
    
            //Make two independent lists by break links.
            ListNode first = head;
            ListNode second = prev.next;
            prev.next = null;    
            
            return join(sortList(first),sortList(second));
        }
        
        private ListNode join(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(-1);
            ListNode dummyIt = dummy;
            while(l1!=null && l2!=null) {
                if(l1.val < l2.val) {
                    dummyIt.next = l1;
                    l1 = l1.next;
                }
                else {
                    dummyIt.next = l2;
                    l2 = l2.next;
                }
                dummyIt = dummyIt.next;
            }
            if(l1!=null) {
                dummyIt.next=l1;
            }
            if(l2!=null) {
                dummyIt.next = l2;
            }
            return dummy.next;
        }    
    }
    

Log in to reply
 

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