利用插入排序对链表进行排序

 下图是对 4-15-9-1插入排序的举例

当if(p.val<=p.next.val){
                p=p.next;}  当不满足条件时 q=p.next  p.next=q.next 

这时候，需要把q节点放到p节点之前的合适位置，即

while(r.next.val<=q.val){
                    r=r.next;
                }

当条件满足时 r后移，当不满足时表示，找到比q节点大的数，那么需要把q节点放入r.next之前

q.next=r.next;
   r.next=q;

具体代码如下：

  public ListNode insertionSortList(ListNode head) {         if(head == null || head.next== null){             return head;         }         ListNode head1 = new ListNode(0);         head1.next=head;         ListNode p = head;         ListNode q;         ListNode r;         while(p != null && p.next != null){             if(p.val<=p.next.val){                 p=p.next;             }else{                 q=p.next;                 p.next=q.next;                 r=head1;                 while(r.next.val<=q.val){                     r=r.next;                 }                 q.next=r.next;                 r.next=q;             }         }                  return head1.next;              }