Code is not elegant but works. No need to introduce any tricks if you really understand the pseudo-code of insertion sort.

```
for i ← 1 to length(A)-1
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
```

It does comparison from the end of the sorted part that avoids useless comparison if the current element is in correct position. Thus, when we do it in linked-list, we also need to do this check although it is O(n) to find insertion position.

Below is my code.

```
class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
dummy = ListNode(-1) # for inserting to the beginning of the list
dummy.next = head
p = head.next
pre = head
while p:
next = p.next
q = dummy
if p.val < pre.val: # avoid unnecessary re-scan
while q.next != p and q.next.val <= p.val:
q = q.next
if q.next != p:
pre.next = p.next
tmp = q.next
q.next = p
p.next = tmp
else:
pre = p # pre pointer update only when no insertion
p = next
return dummy.next
```