Help! why my java merge sort solution only beats 15% submissions?


  • 0
    Y
        public ListNode sortList(ListNode head) {
            //merge sort
            if((head==null)||(head.next==null)){
                return head;
            }
            
            int half_length=getListLength(head)/2-1;// note "-1" 
            ListNode p=head;
            while(half_length>0){
                p=p.next;
                half_length--;
            }
            ListNode s1=sortList(p.next);
            p.next=null;// note p.next=null is between s1 and s2
            ListNode s2=sortList(head);
            head=mergeTwoSortedLists(s1, s2);
            return head;
        }
        int getListLength(ListNode head){
            int length=0;
            while(head!=null){
                head=head.next;
                length++;
            }
            return length;
        }
        ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
            ListNode dummyHead=new ListNode(0);
            ListNode p=dummyHead;
            while((l1!=null)&&(l2!=null)){
                if(l1.val<l2.val){
                    p.next=l1;
                    l1=l1.next;
                }
                else{
                    p.next=l2;
                    l2=l2.next;
                }
                p=p.next;
            }
            p.next=(l1==null)?l2:l1;
            return dummyHead.next;
        }
    }
    

Log in to reply
 

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