public ListNode InsertionSortList(ListNode head) {
for (ListNode iNode = head; iNode != null; iNode = iNode.next)
for (ListNode pre = head, jNode = head, tmp = jNode.next; jNode != iNode && jNode.next != null; tmp = jNode.next)
if (jNode.val > jNode.next.val){
jNode.next = tmp.next;
tmp.next = jNode;
if (pre == jNode) head = pre = tmp;
else{
pre.next = tmp;
pre = tmp;
}
}else{
pre = pre == jNode ? pre : pre.next;
jNode = pre.next;
}
return head;
}
Implement a 15Line C# Solution Without Helper Node


This is closer to the original Pseudo code on WikiPedia https://en.wikipedia.org/wiki/Insertion_sort
Pseudocode of the complete algorithm follows, where the arrays are zerobased:[1]:116
for i ← 1 to length(A)  1 j ← i while j > 0 and A[j1] > A[j] swap A[j] and A[j1] j ← j  1 end while end for