# Maybe the best JAVA solution with code comments

• ``````public class Solution {

}
//record node before insertNode
//rocord node need to be inserted

while(insertNode != null){
//store next insert node
ListNode nextInsert = insertNode.next;
preNode.next = insertNode.next;
}
else if(insertNode.val >= preNode.val){    //insert after tail
preNode = preNode.next;
}
else{                                      //insert between head and tail
//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;
}
}
}
``````

Hope it will helpful. The thinking is very straightforward:

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

• similar solution:

2. after rear
``````public ListNode insertionSortList(ListNode head)
{
return null;

while (currentCheck != null)
{
currentRear.next = currentCheck.next;

{
}
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;
}
}
}

currentCheck=currentRear.next;
}

}``````

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

• @YYZ90 Too clumsy. How about mine below:

``````    public ListNode insertionSortList(ListNode 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;
}