3 IF and 2 WHILE solution in Java with comments


  • 0
    L

    A small trick in the algorithm is that we can just switch values between nodes, in order to remove a node in a linked list without the preceding pointer.

    public ListNode insertionSortList(ListNode head) {
    
    	ListNode result = null;
    	ListNode elem = head;
    
    	while (elem != null) {
    		ListNode resultCur = result;
    
    		if (resultCur == null) {
    			result = new ListNode(elem.val);
    			elem = elem.next;
    			continue;
    			
    		} else {
    			// Run until the last element 
    			while (resultCur.next != null) {
    				if (elem.val > resultCur.val) {
    					resultCur = resultCur.next;
    				} else {
    					break;
    				}
    			}
    			
    			if(elem.val > resultCur.val){
    				// Put the new element in the tail, after "resultCur".
    				ListNode newNode = new ListNode(elem.val);
    				resultCur.next = newNode;
    			
    			}else{
    				// Insert the new element in front of "resultCur" by switching values.
    				ListNode newNode = new ListNode(resultCur.val);
    				resultCur.val = elem.val;
    				
    				newNode.next = resultCur.next;
    				resultCur.next = newNode;	
    			}
    		}
    
    		elem = elem.next;
    	}
    
    	return result;
    }

  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    L

    Thanks for your notice.


Log in to reply
 

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