链表的插入排序

题目描述
使用插入排序对链表进行排序。
示例1
输入
复制
{30,20,40}
返回值
复制
{20,30,40}

#define Node ListNode
#define null NULL

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        if(head==null || head->next==null) return head;
        // write code here
        Node dummy(0);
        Node *p,*q,*t;
        while(head) {
            p = &dummy;
            q = p->next;
            t = head;
            head = head->next;
            while(q && q->val < t->val) {
                p = p->next;
                q = q->next;
            }
            t->next = q;
            p->next = t;
        }
        return dummy.next;
    }
    
    
};