Two 6~8ms optimal solutions, beats >97%


  • 0
    //Use dummy head
    public ListNode insertionSortList(ListNode head) {
        if(head ==null) return null;
        ListNode prev = head, current = head.next;
        head = new ListNode(0); head.next = prev; // Create dummy head
        while (current != null) {
            if(prev.val<=current.val) prev = current; //no need to insert current node
            else{
                    ListNode sortedWalker = head; //need to insert current node
                    while (sortedWalker.next.val < current.val) sortedWalker = sortedWalker.next;
                    prev.next = current.next; //let prev connect to current.next
                    current.next = sortedWalker.next; //insert current node in between sortedWalker and sortedWalker.next
                    sortedWalker.next = current;
            }
           current = prev.next;
       }
       return head.next;
    }
    //Use 4 pointers
       public ListNode insertionSortList(ListNode head) {
        	if(head==null) return head;
        	ListNode current = head.next, prev = head;
        	while(current!=null){
        	    if(prev.val<=current.val)  prev = current; //no need to insert current node in between sortedWalker and sortedRunner
        	    else{//need to insert current node in between sortedWalker and sortedRunner
        		    ListNode sortedRunner = head, sortedWalker = null;
        	    	    while(sortedRunner.val<current.val){
        			    sortedWalker = sortedRunner;
        			    sortedRunner = sortedRunner.next;
        		    }
        		    prev.next = current.next;//let prev connect to current.next
        		    if(sortedWalker==null) head = current;//In case of current node is inserted to be the new head 
        		    else sortedWalker.next = current; //Then insert current node in between sortedWalker and sortedRunner
        		    current.next = sortedRunner;
        	    }
                current = prev.next;
        	}
        	return head;
        }

Log in to reply
 

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