两种写法

写法一

比较啰嗦的写法，将链表分为两个部分去看待，一部分是有序的，一部分是无序的

public static ListNode insertionSortList(ListNode head) {
        //start表示有序的开始
        //end表示有序的结束
        ListNode start=head;
        ListNode end=head;
        while(end.next!=null)
        {    
            //获取到当前的第一个无序的元素
            ListNode cur=end.next;
            //如果当前和之前相比是有序的，就加入到其中，并进行下一次的操作
            if(cur.val>=end.val)
            {
                end=end.next;
                continue;
            }
            //如果是没有序的话，将这个元素单另出来
            end.next=end.next.next;
            //然后从有序的链表第一个开始
            ListNode sort=start;
            ListNode pre=null;
            while(cur.val>sort.val)
            {
                pre=sort;
                sort=sort.next;
            }
            //执行到这个位置的时候，在pre和pre.next之间就是要插入的位置    
            if(pre==null)
            {
                start=cur;//需要改头
                cur.next=sort;
            }else
            {
                pre.next=cur;
                cur.next=sort;
            }
        }
        return start;
    }

写法2

划分没有这么明确，单单是通过pre和cur的遍历

public static ListNode insertionSortList(ListNode head) {

        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null)
        {
            if(pre==null||pre.val<cur.val)//有序的话，直接周
            {
                pre=cur;
                cur=cur.next;
            }else if(pre.val>cur.val)//无序的话，从头开始比较
            {
                ListNode temp=head;
                ListNode temppre=null;
                while(temp.val<cur.val)
                {
                    temppre=temp;
                    temp=temp.next;
                }
                pre.next=cur.next;
                cur.next=temp;
                if(temppre!=null)
                {
                    temppre.next=cur;
                }else
                {
                    head=cur;
                }
                cur=pre.next;//注意每一次cur都要重置，否则就是死循环
            }
        }
        return head;
    }