/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public ListNode insertionSortList(ListNode head) {

         if(head==null||head.next==null)

         return head;

         ListNode pre=head;

         ListNode q=head.next;

         ListNode p=head;

         while(q!=null)

         {

             if(q.val<=head.val)

             {

                 pre.next=q.next;

                 q.next=head;

                 head=q;

                 if(pre.next==null)

                 break;

                 else q=pre.next;

                 p=head;

             }

             else

             if(q.val>=p.val&&q.val<p.next.val)

             {

                 pre.next=q.next;

                 q.next=p.next;

                 p.next=q;

                 if(pre.next==null)

                 break;

                 else q=pre.next;

                 p=head;

             }

             else if(q.val>=p.val&&q.val>p.next.val)

             { p=p.next;

             }

             else if(q.val==p.next.val&&p.next!=q)//用于有重复元素时的排序

             {p=p.next;}

             else {

                 p=head;

                 pre=pre.next;

                 q=pre.next;

             }

             ListNode c=head;

         }

         return head;

     }

 }