Maybe the best JAVA solution with code comments


  • 5
    public class Solution {
    
        public ListNode insertionSortList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            //record node before insertNode
            ListNode preNode = head;
            //rocord node need to be inserted
            ListNode insertNode = head.next;
            
            while(insertNode != null){
                //store next insert node
                ListNode nextInsert = insertNode.next;
                //insert before head
                if(insertNode.val <= head.val){
                    preNode.next = insertNode.next;
                    insertNode.next = head;
                    head = insertNode;
                }
                else if(insertNode.val >= preNode.val){    //insert after tail
                    preNode = preNode.next;
                }
                else{                                      //insert between head and tail
                    ListNode compareNode = head;
                    //start from the node after head, find insert position
                    while(compareNode.next.val < insertNode.val)   compareNode = compareNode.next;
                    //insert
                    preNode.next = insertNode.next;
                    insertNode.next = compareNode.next;
                    compareNode.next = insertNode;
                }
                //get next insert node
                insertNode = nextInsert;
            }
            return head;
        }
    }
    

    Hope it will helpful. The thinking is very straightforward:

    1. Insert before head.
    2. Insert after tail.(no need change the list).
    3. Insert between head and tail.

  • 0
    Y

    similar solution:

    1. before head
    2. after rear
    3. between head and rear
    public ListNode insertionSortList(ListNode head)
    {
    	if (head == null)
    		return null;
    
    	ListNode currentCheck = head.next;
    	ListNode currentHead = head;
    	ListNode currentRear = head;
    	ListNode currentInside = head;
    
    	while (currentCheck != null)
    	{
    		currentRear.next = currentCheck.next;
    
    		if (currentCheck.val < currentHead.val)
    		{
    			currentCheck.next = currentHead;
    			currentHead = currentCheck;
    			currentInside=currentHead;
    		}
    		else if (currentCheck.val >= currentRear.val)
    		{
    			currentCheck.next = currentRear.next;
    			currentRear.next = currentCheck;
    			currentRear = currentCheck;
    		}
    		else
    		{
    			while (true)
    			{
    				if (currentCheck.val >= currentInside.val && currentCheck.val < currentInside.next.val)
    				{
    					currentCheck.next = currentInside.next;
    					currentInside.next = currentCheck;
    					break;
    				}
    				else
    				{
    					currentInside = currentInside.next;
    				}
    			}
    			currentInside=currentHead;
    		}
    		
    		currentCheck=currentRear.next;
    	}
    
    	return currentHead;
    }

  • 0
    S

    @zwangbo
    Can you tell me what would be the time and space complexity of your solution. Very nice solution indeed. Thank you.


  • 0

    @YYZ90 Too clumsy. How about mine below:

        public ListNode insertionSortList(ListNode head) {
        	if(head==null) return head;
        	ListNode current = head.next, prev = head;
        	while(current!=null){
        	    if(prev.val<=current.val) //no need to insert current node in between sortedWalker and sortedRunner
        	        prev = current; 
        	    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.