LeetCode题解之Insertion Sort List

1、题目描述

 

2、题目分析

利用插入排序的算法即可。注意操作指针。

 

3、代码

ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *p = head;
        ListNode *pn = head->next;
        
        while (pn != NULL) {
            pre = dummy;
            p = dummy->next;
            while (p->val < pn->val) {
                p = p->next;
                pre = pre->next;
            }
            
            ListNode *tmp = pn->next;
            pre->next = pn;
            pn->next = p;
            
            while (p->next != pn)
                p = p->next;
            p->next = tmp;
            pn = tmp;
        }
        
        return dummy->next;
        
    }