147-insertion-sort-list

solution

    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        while (head && head->next)
        {
            ListNode *temp = dummy;
            while (head->next->val > temp->next->val && temp != head)
                temp = temp->next;
            if (temp->next!=head->next)
            {
                ListNode *x = head->next->next;
                head->next->next = temp->next;
                temp->next = head->next;
                head->next = x;
            }
            else
            {
                head = head->next;
            }
        }
        return dummy->next;
        
    }