147. Insertion Sort List

Sort a linked list using insertion sort.

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode *current = head;
        while(current && current->next)
        {
            if (current->next->val>current->val)
            {
                current = current->next;
                continue;
            }
            ListNode* tmp= current->next;
            current->next = current->next->next;
            ListNode* search = dummy;
            while(search->next && search->next->val < tmp->val)
            {
                search = search->next;
            }
            tmp->next = search->next;
            search->next = tmp;
        }
        head = dummy->next;
        delete dummy;
        return head;
        
    }
};