Insertion Sort List

题目：

Sort a linked list using insertion sort.

分析：

首先，应用dummy结点

其次，从head + 1开始，因为head本身不用排序

最后，如果符合从小到大，直接向后移动，如果不符合从小到大，才考虑insertion。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    ListNode *insertionSortList(ListNode *head) {
        // write your code here
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode dummy(0);
        dummy.next = head;

        ListNode* prev = head;
        ListNode* curr = head->next;
        while (curr != NULL) {

            if (prev->val <= curr->val) {
                prev = prev->next;
                curr = curr->next;
                continue;
            }

            prev->next = prev->next->next;
            ListNode* temp = &dummy;

            while (temp->next != NULL && temp->next->val < curr->val) {
                temp = temp->next;
            }
            curr->next = temp->next;
            temp->next = curr;

            curr = prev->next;
        }

        return dummy.next;
    }
};