/**
 * Sort a linked list using insertion sort.
 * 
 * Tags: Linkedlist, Sort
 */
class InsertionSortList {
    public static void main(String[] args) {
        
    }
    
    /**
     * Check the list one by one to find a node that has smaller value than 
     * nodes before it and swap
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = new ListNode(0);
        pre.next = head;
		
		/*
		 * pre - check the insertion position from the begining.
		 * p - current element
		 * prev - the element before the current one
		 * c - the p may insert after c.
		 */
        
        for (ListNode p = head.next, prev = head; p != null; prev = p, p = p.next) {// prev -> p
            for (ListNode c = pre; c != prev; c = c.next) {// p is right after prev already.       
                if (c.next.val > p.val) { 
                    prev.next = p.next; // skip p
                    p.next = c.next; // insert between cur and cur.next
                    c.next = p;
                    break;
                }
            }
        }
        return pre.next;
    }
    
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

@@ -430,19 +430,21 @@
 istNode 
-pre
+dummy
  = new L
@@ -463,19 +463,21 @@
         
-pre
+dummy
 .next = 
@@ -495,19 +495,21 @@
 /*%0A%09%09 * 
-pre
+dummy
  - check
@@ -584,17 +584,16 @@
 %09%09 * pre
-v
  - the e
@@ -712,17 +712,16 @@
 ext, pre
-v
  = head;
@@ -735,17 +735,16 @@
 ull; pre
-v
  = p, p 
@@ -760,17 +760,16 @@
  %7B// pre
-v
  -%3E p%0A  
@@ -796,19 +796,21 @@
 ode c = 
-pre
+dummy
 ; c != p
@@ -811,17 +811,16 @@
 c != pre
-v
 ; c = c.
@@ -828,16 +828,30 @@
 ext) %7B//
+c!=pre because
  p is ri
@@ -863,17 +863,16 @@
 fter pre
-v
  already
@@ -922,16 +922,34 @@
 .val) %7B 
+ // ascending sort
 %0A       
@@ -964,17 +964,16 @@
      pre
-v
 .next = 
@@ -1041,32 +1041,21 @@
 ert 
-between cur and cur.next
+right after c
 %0A   
@@ -1167,19 +1167,21 @@
  return 
-pre
+dummy
 .next;%0A 

Update implementation.