Problem

Sort a linked list using insertion sort.

Example

Given 1->3->2->0->null, return 0->1->2->3->null.

Note

插入排序【维基百科】

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

6. 重复步骤2~5

关于插入排序，我所知道的就是从头部开始，将每个数放到合适的位置。在放这个数之前，这个数的目标位置和原始位置之间的数都要先进行后移。然而这是一个in-place的操作，而对于链表而言，我们只要做一个空链表，然后不断加入原链表中的最小元素即可。
cur是原链表head的指针，不断向后扫描；node是空链表dummy的指针，用node.next与cur所指向的结点进行比较，一旦发现排列好的新链表中有大于cur的结点，就把cur放在node.next，然后进行下一轮循环：cur.next作为原链表新的cur，node返回新链表起点dummy。最后，当cur = null，即遍历完整个原链表之后，新链表排序完成。返回dummy.next即可。

Solution

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < cur.val) node = node.next;
            ListNode temp = cur.next;
            cur.next = node.next;
            node.next = cur;
            cur = temp;
        }
        return dummy.next;
    }
}