###### tags: `LeetCode` `Linked List` `Medium`
# LeetCode #147 [Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)
### (Medium)

對鏈結串列進行插入排序。

插入排序算法：

* 插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
* 每次迭代中，插入排序只從輸入數據中移除一個待排序的元素，找到它在序列中適當的位置，並將其插入。
* 重複直到所有輸入數據插入完為止。

---

按照敘述算法實作即可。

/**
 * 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)return nullptr;
        vector<int> store;
        while(head){
            store.insert(upper_bound(store.begin(), store.end(), head->val), head->val);
            head=head->next;
        }
        ListNode *tmp = nullptr, *ans = nullptr, *prev = nullptr;
        for(auto i:store){
            tmp = new ListNode(i);
            if(!prev)ans = tmp;
            else prev->next = tmp;
            prev = tmp;
        }
        return ans;
    }
};

---
作弊法:將元素全部放入數組中, 再進行sort, 最後再將數組職還原成鏈結串列回傳

/**
 * 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)return nullptr;
        vector<int> store;
        while(head){
            store.push_back(head->val);
            head=head->next;
        }
        sort(store.begin(), store.end());
        ListNode *tmp = nullptr, *ans = nullptr, *prev = nullptr;
        for(auto i:store){
            tmp = new ListNode(i);
            if(!prev)ans = tmp;
            else prev->next = tmp;
            prev = tmp;
        }
        return ans;
    }
};