Sort a linked list using insertion sort.

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13         public ListNode insertionSortList(ListNode head) {14         if(head == null)15             return null;16         ListNode helper = new ListNode(0);17         ListNode pre = helper;18         ListNode cur = head;19         while(cur!=null)20         {21             ListNode next = cur.next;22             pre = helper;23             while(pre.next!=null && pre.next.val<=cur.val)24             {25                 pre = pre.next;26             }27             cur.next = pre.next;28             pre.next = cur;29             cur = next;30         }31         return helper.next;32       }33 }

 1 public ListNode insertionSortList(ListNode head) { 2     if(head == null) 3         return null; 4     ListNode helper = new ListNode(0);//helper is the dummy head for the result sorted LinkedList 5     ListNode pre = helper; //pre is the pointer to find the suitable place to plug in the current node 6     ListNode cur = head; //cur is current node, the node to be plugged in the sorted list 7     while(cur!=null) 8     { 9         ListNode next = cur.next; //keep a record of the current node‘s next10         pre = helper;11         while(pre.next!=null && pre.next.val<=cur.val) //use pre to traverse the sorted list to find the suitable place to plug in12         {13             pre = pre.next;14         }15         cur.next = pre.next;// plug in current node to the right place16         pre.next = cur;17         cur = next; //go on to deal with the next node in the unsorted list18     }19     return helper.next;20 }