题目：Sort a linked list using insertion sort.

思路：题目要求我们用插入排序来实现链表排序。我们构建一个当前排好序的链表，然后维护一个变量，不断指向链表中的下一个节点。用变量cur表示当前要插入的节点，每次循环找到cur节点在当前排好序的链表中对应的位置，然后插入进去，然后指向原链表中下一个节点，继续进行插入过程，直到原链表的所有节点都完成，既经过N次迭代后，就得到了排序好的结果。

复杂度：时间O(N^2) 空间O(1)

Attention:

1. 维护一个当前排序好的链表，构建一个虚拟头结点。我们总是将原链表中的下一个节点，插入到新链表中的合适位置。

 ListNode* dummyhead = new ListNode(0);
 ListNode* pre = dummyhead;

//在当前排好的新链表中找到第一个大于cur->val的结点
            while(pre->next != NULL && pre->next->val <= cur->val)
            {
                pre = pre->next;
            }
            
            //当前pre的next结点的值大于cur的值,将cur插入到pre后
            cur->next = pre->next;
            pre->next = cur;

ListNode* next = cur->next;  //维护链表的下一个结点

cur = next;   //cur指向原链表的下一个节点

pre = dummyhead;             //重置pre为新链表头开始

/**
 * 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) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* dummyhead = new ListNode(0);
        ListNode* pre = dummyhead;
        ListNode* cur = head;
        
        while(cur != NULL)
        {
            ListNode* next = cur->next;  //维护链表的下一个结点
            pre = dummyhead;             //重置pre为新链表头开始
            
            //在当前排好的新链表中找到第一个大于cur->val的结点
            while(pre->next != NULL && pre->next->val <= cur->val)
            {
                pre = pre->next;
            }
            
            //当前pre的next结点的值大于cur的值,将cur插入到pre后
            cur->next = pre->next;
            pre->next = cur;
            cur = next;   //cur指向原链表的下一个节点
        }
        return dummyhead->next;
    }
};

这道题，刚开始我也有考虑在原来的链表中进行插入操作，就和数组的操作有点像，因为我们要将当前元素插入已经排好序的链表的合适位置上，这样我们不仅需要比较大小，还需要保证pre节点不能跨过当前节点，这样就无法保证我们的插入时正确的。如{3,4,1}， 第一次迭代pre->next停在3, cur在4，我们并不能将4插到3前面。所以对于链表，在原链表的操作是比较复杂的。需要新建一个排序好的链表进行插入操作，可以避免很多判断。

[C++]LeetCode: 126 Insertion Sort List (插入排序链表)