对链表进行插入排序

思路：

1.只要还没有走到链表的倒数第二个节点，就表明插入排序还没有完成，就继续进行插入排序

2.对于每次插入排序，都需要遍历整个链表，只要是保持升序的就跳过，直到找到第一个打破升序的节点

3.先判断一下如果发现p.next为null，就表明原先已有的链表就是有序的，就可以直接返回头结点，就结束

4.否则就创建新的一个节点用于存这个节点的值

5.进行插排操作，对于插排操作分为两种情况：一种是插入链表的头结点前，这时候就将这个新的节点连在链表的头结点

不要忘记更新链表的头结点为该新的节点；第二种情况就是将节点插入两个节点的中间，就用一个while循环遍历找到第一个大于该节点的值。

6.将这个节点进行完插入排序后，就将原位置的这个节点进行删除

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    //对链表进行插排操作
    public ListNode insertionSortList (ListNode head) {
        ListNode p=head;
        //只要还剩下大于一个节点，即表明还有节点没有进行插排
        while(p.next!=null){
            //每次用一个while循环去遍历，只要还要是保持升序的，就是表明是这部分时有序的，找到第一个没有保持有序的节点
            while(p.next!=null&&p.next.val>p.val){
                p=p.next;
            }
            //先判断一下如果p.next是null而导致退出循环的,就是表明原来的链表就已经是有序的了，直接返回头结点结束
            if(p.next==null){
                return head;
            }
            //否则就创建一个新的节点用于存这个节点的值
            ListNode temp=new ListNode(p.next.val);
            //然后就可以进入插排操作，但是对于插排操作，又根据插入的位置分为两种情况
            //如果发现该点的值小于头结点的值，就插在链表的最前面的位置
            //并且不要忘记更新头结点！！！
            //总结：对于插入个节点：1.如果插入到链表的头节点的前面,就将插入的点的指向头结点，并且更新链表的头结点
            //2.如果插入链表的中间，就需要将前一个节点指向新插入的节点，将 新插入的节点指向原先的下一个节点
            if(temp.val<head.val){
                temp.next=head;
                head=temp;
            }else{
                //否则，就先用一个while进行遍历，找到第一个大于需要插入的节点的值的节点，将这个新的节点插入这个节点的前面
                ListNode t=head;
                while(t.next!=null&&t.next.val<temp.val){
                    t=t.next;
                }
                temp.next=t.next;
                t.next=temp;
            }
            //完成插排操作后，就将原先位置的这个节点进行删除 
            p.next=p.next.next;
        }
        return head;
    }
}