Insertion Sort List

Description:

Sort a linked list using insertion sort.

Code:

 ListNode* insertionSortList(ListNode* head) {
        if (head == NULL)
            return NULL;
        ListNode* headNode = new ListNode(0);
        headNode->next = head;
        
        ListNode* p = head->next;
        head->next = NULL;
        while (p)
        {//p为待排序节点
            ListNode* q = headNode;
            while ( q->next!=NULL && q->next->val <= p->val)
                q = q->next;
                
            ListNode* tempQ = q->next;
            ListNode* tempP = p->next;
            q->next = p;
            p->next = tempQ;
            p = tempP;
         
        }
        
        head = headNode->next;
        headNode->next = NULL;
        delete headNode;
        return head;
    }

PS:

题目简单，但代码却写了很久，中间指针的修改过程一直思路紊乱。