题目：

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list</small>

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

思路：

本题已经很明确的告诉了咱们是插入排序。但本题特殊在这是对链表进行插入排序。按照插入排序的想法，首先找到位置为i的元素，在查找i之前的元素如果有比位置i上的元素大的值则开始进行插入操作。

假设查找到的i之前的元素的位置为j。则在j之前新插入一个结点，结点的元素值就是位置i的元素值。之后再将位置i的元素删掉。

注意：新设一个结点previous，指向题目所给的链表。最后返回previous.next。这步操作可以避免在替换或删除头结点时的麻烦操作。

代码：

    public ListNode insertionSortList(ListNode head) {
        if(head == null)
            return null;
        if(head.next == null)
            return head;
        
        ListNode previous = new ListNode(0);
        previous.next = head;
        ListNode node2 = head.next;
        while(node2 != null){
            ListNode node1 = previous;
            while(node1.next != node2){
                if(node2.val < node1.next.val){
                    ListNode newnode = new ListNode(node2.val);
                    newnode.next = node1.next;
                    node1.next = newnode;
                    deleteNode(head, node2);
                    break;
                }
                node1 = node1.next;
            }
            node2 = node2.next;
        }
        return previous.next;
    }
    
    private void deleteNode(ListNode head, ListNode node2){
        ListNode node = head;
        while(node.next != node2){
            node = node.next;
        }
        node.next = node2.next;
    }