147. insertion sort list

Sort a linked list using insertion sort.

这题是用插入排序排序一个链表。插入排序基本思想：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

timg.gif

对于数组的话大概是这样子，外层循环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