/**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     struct ListNode *next;

  * };

  */

 struct ListNode* insertionSortList(struct ListNode* head)

 {

     struct ListNode *p;

     p=head;

     int count=;

     while(p!=NULL)

     {

         count++;

         p=p->next;

     }

     int *array;

     array=(int *)malloc(count*sizeof(int));

     p=head;

     int i=,j,k;

     while(p!=NULL)

     {

         array[i]=p->val;

         p=p->next;

         i++;

     }

     for(i=;i<count;i++)

     {

         for(j=i-;j>=;j--)

         {

             if(array[j]<array[i])

                 break;

         }

         if(j!=i-)

         {

             int tmp=array[i];

             for(k=i-;k>j;k--)

             {

                 array[k+]=array[k];

             }

             array[k+]=tmp;

         }

     }    

     i=;

     struct ListNode *q;

     q=head;

     while(q!=NULL)

     {

         q->val=array[i];

         q=q->next;

         i++;

     }

     return head;

 }