leetcode-Insertion Sort List

题目链接：https://leetcode.com/problems/insertion-sort-list/

题目分析：

其实搞清楚指针的变化就很容易

如下是代码：

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode dummy(-1);
        dummy.next = head;

        ListNode *pre = head;
        ListNode *cur = head->next;
        while(cur != NULL)
        {
            if(cur->val >= pre->val)
            {
                pre = cur;
                cur = cur->next;
            }
            else
            {
                ListNode *insertPre = &dummy;
                ListNode *insertCur = dummy.next;
                while(insertCur->val < cur->val)
                {
                    insertPre = insertCur;
                    insertCur = insertCur->next;
                }
                pre->next = cur->next;
                cur->next = insertCur;
                insertPre->next = cur;
                cur = pre->next;
            }
        }
        return dummy.next;
    }
};