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