My intuitive solution - NOT a good solution, but for your reference


  • 0
    L

    This is the first solution I came up with, it passes the OJ, but has a bad running time (74ms). I share it with you folks just because I don't see any similar solution here in the discussion. Comments welcome.

    public ListNode insertionSortList(ListNode head) {
    
    	ListNode outer = head;
    	ListNode inner;
    
    	while (outer != null) {
    		inner = head;
    		while (inner.val <= outer.val && inner != outer) {
    			inner = inner.next;
    		}
    
    		ListNode insertNode = inner;
    		int valInsert = outer.val;
    		int valNext = inner.val;
    		while (inner != outer) {
    			int temp = inner.next.val;
    			inner.next.val = valNext;
    			valNext = temp;
    			inner = inner.next;
    		}
    
    		insertNode.val = valInsert;
    		outer = outer.next;
    	}
    
    	return head;
    }
    

    Also, I see most solutions in the discussion uses the following code to move the inner loop pointer

    		while (prev.next != null && prev.next.val < cur.val) {
    			prev = prev.next;
    		}
    

    I think it's better to use "<=" instead of "<", this way the sort is stable.

    		while (prev.next != null && prev.next.val <= cur.val) {
    			prev = prev.next;
    		}
    

    Thanks.


Log in to reply
 

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