题解 | #对链表进行插入排序#

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* p = head;
        while(p->next)
        {
            while(p->next && p->next->val>p->val) p = p->next; 
            if(!p->next) return head;
            ListNode *q = new ListNode(0);
            q->val = p->next->val;
            if(q->val<head->val) 
            {
                q->next = head;
                head = q;
            }
            else{
                ListNode *t = head;
                while(t->next && t->next->val<q->val) t = t->next;
                q->next = t->next;
                t->next = q;
            }
            p->next = p->next->next;
        }
        return head;
    }
};