Detail java solution with complexity analysis


  • 2
    Z
    /**
     * Time complexity: BEST CASE : COMPLETELY ASCENDING/DESENDING ORDER --> O(n)
     *                  WORST CASE : EVERY TIME INSERT JUST BEFORE THE MAX NODE
     *                               0+1+2+....+(n-1) --> O((n2-n)/2) --> O(n2)
     * Memory complexity: In-place --> O(1)
     */
    public ListNode insertionSortList(ListNode head) {
        
        //EDGE CASE
        if(head==null || head.next==null) return head;
        
        //INIT NODES
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        ListNode max = head; //CURRENT MAX VALUE NODE (TAIL)
        
        //INSERTION SORT
        while(cur!=null){
            while(cur!=null && cur.val>=max.val){ //SKIP ACSENDING SEQUENCE AND UPDATE THE MAX NODE
                max = cur;
                cur = cur.next;
            }
            if(cur==null) break;
            
            ListNode temp = cur.next; //STORE THE NEXT NODE BEFORE INSERTION
            if(dummy.next.val>cur.val){ // INSERT BEFORE HEAD NODE, THIS NODE BECOMES NEW HEAD
                cur.next = dummy.next;
                dummy.next = cur;
            }else{
                ListNode pre = dummy.next;
                while(pre.next!=null){
                    if(cur.val>=pre.val && cur.val<=pre.next.val){ //INSERT BETWEEN HEAD AND MAX NODE
                        cur.next = pre.next;
                        pre.next = cur;
                        break;
                    }
                    pre = pre.next;
                }
            }
            cur = temp;  //UPDATE POINTERS HERE, REALLY IMPORTANT, OTHERWISE YOU'LL END UP WITH A INFINITE LOOP!
            max.next = temp;
        }
        
        //RETURN HEAD
        return dummy.next;
    }

Log in to reply
 

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