Why my method is exceeding time???


  • 0
    D

    public class Solution {

    public  ListNode sortList(ListNode head) {
        ListNode head2 =null;
        if(head==null||head.next==null){
        	System.out.println("I am here");
            return head;
        }
        
        else{
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null){
            	 fast=fast.next;
                
                    if(fast!=null&&fast.next!=null){
                        fast=fast.next;
                        slow=slow.next;
                    }
                
            }
            head2=slow.next;
            slow.next=null;
        }
        ListNode newHead = merge( sortList(head),sortList(head2));
        return newHead;
        
    }
    
    public ListNode merge(ListNode a,ListNode b){
        ListNode combined=null;
        ListNode combinedHead=null;
         if(a==null&&b!=null){
            return b;
        }else if(a!=null && b==null){
            return a;
        }
        while(a!=null&&b!=null){
            if(a.val>b.val){
              if(combined==null){
                  combined=b;
                  combinedHead=b;
              }else{
                  combined.next=b;
                  combined=combined.next;
              }
              b=b.next;
            }else{
                  if(combined==null){
                  combined=a;
                  combinedHead=a;
              }else{
                  combined.next=a;
                  combined=combined.next;
              }
              a=a.next;
            }
        }
        
        if(a==null&&b==null){
            return combinedHead;
            }
            else{
              if(a!=null){
                  combined.next=a;
              }
              if(b!=null){
                  combined.next=b;
              }
            }
       
        combined.next=null;
        return combinedHead;
    }
    

    }


  • 0
    K

    I had the same issue, mergsort would always be o(NlogN)


Log in to reply
 

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