[数据结构与算法]对链表进行插入排序 C语言

新建一个新的头结点，然后依次将原链表的结点按顺序插入到新的表中。
p表示原链表中待插入的结点。
q表示新链表中待插入位置的前驱节点。
temp保留p的后继结点信息。

struct ListNode* insertionSortList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode newHead;        //新建头结点
    newHead.next = head;        //
    struct ListNode *p = head->next,*q;     //定义两个指针，分别指向
    newHead.next->next = NULL;
    while(p)
    {
        q=&newHead;
        while(q->next != NULL && q->next->val < p->val)
        {
            q=q->next;
        }
        //退出循环时q指针的后继结点大于p 或者指向空
        struct ListNode *temp = p->next;
        p->next = q->next;
        q->next = p;
        p=temp;
    }
    return newHead.next;
}