Time limit exceeded (recursive mergesort, Java) - any help?


  • 0
    E

    My code seems to be running in O(N^2) time, but I'm having trouble figuring out how to refactor it so that it runs in O(NlogN). Any suggestions?

    public class Solution{
    
      public static ListNode sortList(ListNode head) {
        if ( head == null || head.next == null ){ return head; }
        else{
          head = merge(sortList(splitNode(head)), sortList(head));
        }
        return head;
      }
    
      public static int getSize(ListNode head) {
        int i=1;
        while (head.next != null){ i++; head = head.next;}
        return i;
      }
    
      public static ListNode splitNode(ListNode head){
        int halfSize = getSize(head)/2;
        ListNode middleNode = head;
        ListNode middleNodePre = head;
        for(int i=0; i<halfSize; i++){
          middleNode = middleNode.next;
          if(i < halfSize-1){ middleNodePre = middleNode; }
        }
        middleNodePre.next = null;
        return middleNode;
      }
    
      public static ListNode merge(ListNode a, ListNode b){
        ListNode result;
        if (a == null && b == null){ return null; }
        else if (a == null) { result = new ListNode(b.val); b=b.next; }
        else if (b == null) { result = new ListNode(a.val); a=a.next; }
        else{
          if (a.val < b.val){ result = new ListNode(a.val); a=a.next; }
          else{ result = new ListNode(b.val); b=b.next; }
        }
    
        while(!(a == null && b == null)){
          if (a == null) { add(result, b.val); b = b.next; }
          else if (b == null) { add(result, a.val); a = a.next; }
          else{
            if (a.val < b.val){ add(result, a.val); a= a.next; }
            else{ add(result, b.val); b = b.next; }
          }
        }
        return result;
      }
    
      public static void add(ListNode a, int val){
        ListNode currentNode = a;
        while (currentNode.next != null){
          currentNode = currentNode.next;
        }
        currentNode.next = new ListNode(val);
      }
    
    }
    

    Thanks a lot!


  • 1
    S

    By using fast and slower iterator, take a look at this post


  • 2
    B

    Yeah, your program runs in O(n^2) time. I think the "add()" function is unnecessary. You try to define a pointer in the "merge()" to show the current node. When a new node is added into the list, the pointer will point at the next element and it costs only O(1). It's no need to cost O(n) time just to point out where the current node is. I give you my code

    public class sortList {

    public static void main (String[] args) {
        ListNode ln1 = new ListNode(3);
        ListNode ln2 = new ListNode(4);
        ListNode ln3 = new ListNode(1);
        ln1.next = ln2;
        ln2.next = ln3;
        ListNode ln = sortList(ln1);
        while (ln != null) {
            System.out.print(ln.val);
            ln = ln.next;
        }
    }
    
    public static ListNode sortList(ListNode head) {
        ListNode pointer = head;
        ListNode head2 = null;
        int count = 1;
    
        if (head == null)
            return null;
    
        if (head.next == null)
            return head;
    
        while (pointer.next != null) {
            count++;
            pointer = pointer.next;
        }
    
        pointer = head;
    
        for (int i = 1; i < count / 2; i++) {
            pointer = pointer.next;
        }
    
        head2 = pointer.next;
        pointer.next = null;
    
        return merge(sortList(head), sortList(head2));
    }
    
    public static ListNode merge(ListNode head1, ListNode head2) {
        ListNode p1 = head1, p2 = head2;
        ListNode newHead = new ListNode(0);
        ListNode p = newHead;
    
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val){
                p.next = p1;
                p = p1;
                p1 = p1.next;
            }
    
            else {
                p.next = p2;
                p = p2;
                p2 = p2.next;
            }
        }
    
        while (p1 != null) {
            p.next = p1;
            p = p1;
            p1 = p1.next;
        }
    
        while (p2 != null) {
            p.next = p2;
            p = p2;
            p2 = p2.next;
        }
        
        return newHead.next;
    }
    

    }

    enter code here

  • 0
    E

    Thanks for your help guys, I was able to get it working after I got rid of the add method!


Log in to reply
 

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