需要注意：一开始虚拟头结点dummynode并没有指向head,用第一次循环的Pre->next指向cur来连接。如果一开始连接了，反而不对。

struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};class Solution {
public:ListNode* insertionSortList(ListNode* head) {ListNode* dummynode = new ListNode(0);ListNode* cur = head;ListNode* pre = dummynode;while (cur != nullptr){while (pre->next != nullptr && pre->next->val < cur->val){pre = pre->next;}  //找本轮cur对应的pre指针位置ListNode* next = cur->next;  //上图中的步骤1到5cur->next = pre->next;pre->next = cur;pre = dummynode;cur = next;}return dummynode->next;}
};