[数据结构与算法]147. 对链表进行插入排序--插入排序思想

思路：
　　链表的一个通用思路就是这样，把原始链表存到一个数组里面，然后用排序算法或者什么排序好，然后对他们的next操作就能得到规定排序的链表了。只是增加了空间复杂度。在这里的排序算法是插入排序！！第一次固定一个值认为排序完成，每次位移来让增加的数在原数组排序完成。
　　首先定位当前索引的前一个索引j，判断当前值是不是比前一个索引下标对应的数组值要小，如果小了肯定要插入所以a[j]一定要后移，所以a[j+1]=a[j]，然后减少索引，再次判断已经大了。那就定居把，就a[j+1]=temp。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head==nullptr)
            return head;
        ListNode*temp=head;
        vector<ListNode*>res;
        while(temp){
            res.push_back(temp);
            temp=temp->next;
        }
        int pre=head->val;
        for(int i=1;i<res.size();i++){
            int temp=res[i]->val;
            ListNode* T=res[i];
            int j=i-1;
            while(j>=0 && temp<res[j]->val){
                res[j+1]=res[j];
                j--;
            }
            res[j+1]=T;
        }
        ListNode* dump=res[0];
        for(int i=0;i<res.size()-1;i++){
            res[i]->next=res[i+1];
        }
        res[res.size()-1]->next=nullptr;

        return dump;
    }
};