Insertion Sort List

一道在链表上进行插入排序的题目，假设在数组上，插入排序的写法不难，但是数据结构改为链表，还是有点儿麻烦的。首先看下题目：

Sort a linked list using insertion sort.

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

对于链表进行插入排序，首先，我们得定位到head之后的节点，然后比较它之前的所有节点。当它比某个节点的值小的时候，插入到它前面。所以这里有一个交换的过程，逻辑主要在交换。

在交换节点的时候有几种情况需要处理，一种是要交换的节点为head节点，那么我们每次交换的时候必须也要更新head节点的值，另一种情况不是head节点，那么我们需要把小的节点插入到两个节点之间。

另外一个细节就是，我们需要维护一个当前需要进行插入排序的节点的前一个节点，假设每次都进行遍历进行查找，肯定会降低效率。所以我们在初始的时候，将tail节点设置为head，当下一个节点插入在它前面的节点之前的时候，我们不必更新tail的值，因为它还是作为下一个要进行插入排序元素的前一个元素；当不需要进行交换的时候，也就是当前节点比它之前所有的节点都大的时候，我们需要把tail节点取下一个节点作为tail，当然tail也就是当前节点。

除了这些细节，其它都比较好处理，贴一个自己的实现：

ListNode* insertionSortList(ListNode* head) {
    if (nullptr == head) {
        return head;
    }
    ListNode *node = head->next;
    ListNode *tail = head;
    int maxStep = 1;
    while (node != nullptr) {
        ListNode *next = node->next;
        ListNode *prev = nullptr;
        ListNode *cur = head;
        int i = 0;
        for (i; i < maxStep; i++) {
            if (node->val < cur->val) {
                tail->next = node->next;
                node->next = cur;
                if (nullptr == prev) {
                    head = node;
                } else {
                    prev->next = node;
                }
                break;
            }
            prev = cur;
            cur = cur->next;
        }
        if (i >= maxStep) {
            tail = tail->next;
        }
        ++maxStep;
        node = next;
    }
    return head;
}