Sort a linked list using insertion sort.

 

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     struct ListNode *next; 6  * }; 7  */ 8 struct ListNode* insertionSortList(struct ListNode* head)  9 {10     struct ListNode *p;11     p=head;12     int count=0;13     while(p!=NULL)14     {15         count++;16         p=p->next;17     }18 19     int *array;20     array=(int *)malloc(count*sizeof(int));21 22     p=head;23     int i=0,j,k;24     while(p!=NULL)25     {26         array[i]=p->val;27         p=p->next;28         i++;29     }30 31     for(i=1;i
     
      =0;j--)34         {35             if(array[j]
      
       j;k--)43             {44                 array[k+1]=array[k];45             }46             array[k+1]=tmp;47         }48     }    49 50     i=0;51     struct ListNode *q;52     q=head;53     while(q!=NULL)54     {55         q->val=array[i];56         q=q->next;57         i++;58     }59 60 61     return head;62 }