Sort a linked list using insertion sort.
这题是用插入排序排序一个链表。插入排序基本思想：
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
对于数组的话大概是这样子，外层循环i从1开始，arr[i]表示先把target保存起来，因为等会儿要平移的，插入排序不是swap，而是要向右平移出一个坑位；内循环j从i-1开始找插入位置，如果arr[j]比target大，就把arr[j]依次向右平移。
直到target >= arr[j - 1]的时候，arr[j] = target;把新元素插到j-1右边的j处（如果条件是target < arr[j - 1]，遇到相等元素会插入到左边）。
插入排序，已有的元素的顺序都是正确的。就像扑克牌一样，抓到新的牌之前的顺序都是好的(http://www.cnblogs.com/xiaoming0601/p/5862793.html)。
for (i = 1; i < n; i++)
{
j = i;
target = arr[i];
while (j > 0 && target < arr[j - 1])
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
回到链表，我们也是定义一个cur结点，从head开始向后，相当于外循环；一个pre结点，用while寻找该插入的位置，最后找到之后，把cur接进pre和pre.next之间，相当于内循环，但是这个内循环是从前往后的。注意，这里仍然没有用到swap，而是结点的插入。链表不存在坑位平移的问题，想插入一个node只需要拼接首位就行了。仍要注意，在拼接cur节点之前，要把cur.next保存起来，才能找到下一个cur的位置。
public static ListNode insertionSortList(ListNode head) {
if (head == null) return null;
ListNode fakeHead = new ListNode(-1);
ListNode pre = fakeHead;
ListNode cur = head;
while (cur != null) {
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
//在把cur.next重定位（插入到pre和pre.next之间）之前，必须要把cur.next保存下来，这样才能cur = next开始下一次循环
ListNode next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
pre = fakeHead;
}
return fakeHead.next;
}
有个值得思考的地方，这题并没有fakeHead.next = head把fakeHead跟head连接起来，这是因为pre每次结束都会指向fakeHead：
pre = fakeHead;
这不仅仅是说pre每次都从头开始，而且 pre.next = cur;
改变的时候，fakeHead的长度是一直在变的，只不过fakeHead的头结点一直停留在-1，而pre是不停变长的。
pre当前的节点值变成了-1，next也变成了fakeHead的next。fakeHead会随着循环一直变化，但首节点一直是-1。 pre = fakeHead;这一句每次循环结束把pre拉回起点，下一次内循环遍历的距离就长一点。
reference
http://www.cnblogs.com/xiaoming0601/p/5862793.html
