```
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null) return head;
//1. There's no requirement of in-place or constant space, so we create a new list(result list) to store result, its head is dummy.
ListNode dummy = new ListNode(0);
//2. Traverse all nodes in unsorted list, for each node(node n) inside unsorted list, traverse through the result list to find the first node whose value is larger than current node(node n).
while(head!=null){
ListNode resultTraverse = dummy;
while(resultTraverse.next!=null&&resultTraverse.next.val < head.val){
resultTraverse = resultTraverse.next;
}
//3. Once we've found the larger node in result list, we can insert current node(node n) before the found larger node in result list.
ListNode temp = head.next;
head.next = resultTraverse.next;
resultTraverse.next = head;
head = temp;
}
return dummy.next;
// How to insert a node(from another list) before a particular node in result list?
// Unsorted list: 1->2->3, result list: D->5, assume we want to insert nodeWithValue1 before nodeWithValue5, we know the dummy node(node D) of result list.
// 1. Store list next to nodeWithValue1: ListNode temp = nodeWithValue1.next
// 2. Link nodeWithValue1 to nodeWithValue5: nodeWithValue1.next = D.next.
// (After step 2 the list will be: 1->5)
// 3. Link dummy node to nodeWithValue1: D.next = nodeWithValue1
// (After step 3 the list will be: D->1->5)
// Go the next node in unsorted list: head = temp
// (Now the pointer in unsorted list will point to nodeWithValue2)
}
```

}