题目：
Sort a linked list using insertion sort.
题解：
Insertion Sort就是把一个一个元素往已排好序的list中插入的过程。
初始时，sorted list是空，把一个元素插入sorted list中。然后，在每一次插入过程中，都是找到最合适位置进行插入。
因为是链表的插入操作，需要维护pre，cur和next3个指针。
pre始终指向sorted list的fakehead，cur指向当前需要被插入的元素，next指向下一个需要被插入的元素。
当sortedlist为空以及pre.next所指向的元素比cur指向的元素值要大时，需要把cur元素插入到pre.next所指向元素之前。否则，pre指针后移。最后返回fakehead的next即可。
代码如下：
1 public ListNode insertionSortList(ListNode head) {
2 if(head == null||head.next == null)
3 return head;
4 ListNode sortedlisthead = new ListNode(0);
5 ListNode cur = head;
6 while(cur!=null){
7 ListNode next = cur.next;
8 ListNode pre = sortedlisthead;
9 while(pre.next!=null && pre.next.val<cur.val)
10 pre = pre.next;
11 cur.next = pre.next;
12 pre.next = cur;
13 cur = next;
14 }
15 return sortedlisthead.next;
16 }
2 if(head == null||head.next == null)
3 return head;
4 ListNode sortedlisthead = new ListNode(0);
5 ListNode cur = head;
6 while(cur!=null){
7 ListNode next = cur.next;
8 ListNode pre = sortedlisthead;
9 while(pre.next!=null && pre.next.val<cur.val)
10 pre = pre.next;
11 cur.next = pre.next;
12 pre.next = cur;
13 cur = next;
14 }
15 return sortedlisthead.next;
16 }