1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *insertionSortList(ListNode *head) 12     {13         14         if(head == NULL || head->next == NULL)15             return head;16         17         vector<int> vec;18         ListNode *p = head;19         while(p != NULL)20         {21             vec.push_back(p->val);22             p = p->next;23         }24         25         for(int i = 1; i < vec.size(); i++)26         {27             int tmp = vec[i];28             int j;29             for(j = i; j > 0 && tmp < vec[j-1]; j--)30                 vec[j] = vec[j-1];31                 32             vec[j] = tmp;33         }34         35         p = head;36         for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++, p = p->next)37             p->val = *it;38             39         return head;40     }41 };