147. Insertion Sort List(JAVA链表的

思路

1. 先判断边界输入。
2. 拆出一个链表元素，head指针移动，直到head为空。
3. 拿拆出的元素与新建的排好序的链表比较，看插在哪里。有三种方式，插在开头，插在中间，插在末尾。插入后把指针指到此链表开头，跳出循环。

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode p1 = new ListNode(-999);
        ListNode p2 = p1;
        ListNode p3 = p1;
        while(head!=null){
            ListNode tmp = new ListNode(head.val);
            head = head.next;
            if(p1.next==null){
                p1.next = tmp;
                continue;
           } 
            while(p1.next!=null){
                if(tmp.val<p1.next.val){
                    ListNode tmp1 = p1.next;
                    p1.next = tmp;
                    tmp.next = tmp1;
                    p1 = p2;
                    break;
                }
                else
                    p1 = p1.next;
            }
            if(p1.next==null){
            p1.next = tmp;
            p1 = p2;
            }
        }
        return p3.next;     
}
}