Insertion Sort List

原题链接Insertion Sort List

对链表进行插入排序

插入排序初始是一个空容器，每遇到一个元素后，在容器中找到该元素应该插入的位置，将其插入即可

对于链表而言，首先初始化一个空链表即可，然后一个一个节点插入

代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto header = new ListNode(INT32_MIN);
        while(head)
        {
            auto node = header;
            while(node->next && node->next->val < head->val)
                node = node->next;
            auto next = head->next;
            head->next = node->next;
            node->next = head;
            head = next;
        }
        head = header->next;
        delete header;
        return head;
    }
};