class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummy = new ListNode(-1);
        for (auto p = head; p; )
        {
            auto cur = dummy, nxt = p->next;
            while (cur->next && cur->next->val <= p->val)   cur = cur->next;
            p->next = cur->next;
            cur->next = p;
            p = nxt;
        }
        return dummy->next;
    }
};