Time Limit Exceeded?


  • 0
    L

    Not sure why it exceeds, here is my code.
    I am little confused because it's normal for insertion sort take O(n^2) time to complete sorting.

     public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode resHead = null;
        ListNode resTail = null;
        while( head != null){
            ListNode curr = head;
            head = head.next;
            //if it's the first node, we can set resHead and resTail
            if( resHead == null){
                resHead = curr;
                resTail = curr;
                resTail.next = null;
            // if the current node is smaller than head, we insert before the resHead
            } else if(curr.val <= resHead.val){
                curr.next = resHead;
                resHead = curr;
            // if the current node is larger than tail, we insert after the resTail
            } else if(curr.val >= resTail.val){
                resTail.next = curr;
                resTail = curr;
                resTail.next = null;
            // otherwise, when the current node's value is in the middle, 
            // we should go through the result list to find the right insertion position
            } else {
                ListNode findPos = resHead;
                while(findPos != null){
                    if(findPos.next == null || curr.val < findPos.next.val){
                        curr.next = findPos.next;
                        findPos.next = curr;    
                        break;
                    }
                    findPos = findPos.next;
                }
            }
        }
        return resHead;
    }

  • 0
    S

    Could you please update your post with explanation of algorithm and comments in code? People barely help on raw code. Thanks.


  • 0
    L

    thanks for reminder, i updated the comments


  • 2
    S

    I go through your code, found nothing wrong. Then I submit it to the OJ, it passed anyway.

    However, I thought the last part of your code could be neater, like this:

            ListNode findPos = resHead;
            while(curr.val > findPos.next.val){
                findPos = findPos.next;
            }
            curr.next = findPos.next;
            findPos.next = curr;  
    

  • 0
    L

    Thanks for your reply, your suggestion is very helpful!


Log in to reply
 

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