对链表进行插入排序

插入排序就是默认左边第一个是已排序好的状态，然后在剩下的数中依次拿出来进行插入操作。

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode start = head;  //已排序子链表头
        ListNode end = head;    //已排序子链表尾

        ListNode p = end.next;

        while(p != null){
            //先跟头比较
            if(start.val >= p.val){
                end.next = p.next;
                p.next = start;
                start = p;
            //跟尾比较
            }else if(end.val <= p.val){
                end = p;
            }else {     //插入子链表中
                end.next = p.next;
                ListNode temp = start;
                while(temp.next.val <p.val) temp = temp.next;
                p.next = temp.next;
                temp.next = p;
            }

            p = end.next;
        }
        return start;
    }
}