对链表进行插入排序。从第一个元素开始，该链表可以被认为已经部分排序。每次迭代时，从输入数据中移除一个元素，并原地将其插入到已排好序的链表中。

力扣原题：

先贴代码：

public class Solution147 {
    public ListNode insertionSortList(ListNode head) {
        //当链表为空时，不需排序，直接返回
        if (head == null){
            return head;
        }
        //创建一个虚拟头节点，方便处理头节点
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        //ret为待排序的节点
        ListNode ret = head.next;
        //进入循环，直到待排序的节点为空（不存在待排序的节点）
        while (ret != null){
            //情况1：头节点小于等于待排序节点
            if (head.val <= ret.val){
                head = head.next;
            //情况2：头节点大于待排序节点
            }else {
                //新建一个cur节点来寻找前面有序链表中大于待排序节点的节点，插入它的前面
                ListNode cur = newhead;
                while (cur.next.val <= ret.val){
                    cur = cur.next;
                }
                head.next = ret.next;
                ret.next = cur.next;
                cur.next = ret;
            }
            ret = head.next;
        }
        return newhead.next;
    }
}

思路解析：

本题中要求我们使用插入排序进行解题，那么什么是插入排序呢？

1、插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2、每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，       并将其插入。
3、重复直到所有输入数据插入完为止。

由上可知，我们先需要在链表中标记一个节点，记为ret待排序节点。将这个节点和链表的头节点进行比较判断大小，若ret节点大于等于头节点，则说明该节点应该排在头节点的后面，这样我们就得到了一小段的有序链表。ret节点为该有序链表的尾巴节点。

使头节点和ret节点都后移一位，这样头节点就又成了有序链表中的尾巴节点（之前头节点的前面没有节点，只有它一个节点，默认为有序链表的尾巴节点）。

不断的将后面的节点与前面有序链表的尾巴节点进行比较，大于尾巴节点则在后面，若小于尾巴节点，就会进入前面的有序链表再和有序链表里的各节点比较，找到大于待排序链表的节点，插入到它的前面。

如下图（图画的不好勿怪），若ret大于等于head，则不需要插入；若ret小于head，则进入head前面的有序链表再次排序找合适的位置（找到大于ret的节点，放在这个节点的前面）：

至于为什么不是再前面有序链表中找小于ret节点的节点排在它的后面？因为若后面还有大于ret小于head的节点的话，那么再进入前面的链表的时候就会混乱，无法再排序。