```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null)return null;
if(head.next == null)return head;
ListNode now = head.next, h = head, t=head, p=head, q=head;
while(now!=null){
if(now.val <= h.val){
// current value is less than head value, so update head
t.next = now.next;
now.next = h;
h = now;
}else{
p=h;
q=p;
// find the position to insert current value
while(p.val<now.val){
if(p==now)break;
q=p;
p=p.next;
}
// p==now because current value is the greatest value evaluated so far
// just set current value as new tail
if(p==now)t=t.next;
else{
t.next = now.next;
now.next = p;
q.next = now;
}
}
// continue to evaluate next value
now = t.next;
}
return h;
}
}
```