147.对链表进行插入排序

两天宇宙人

2020-01-11

🥧模仿数组的实现

注意pre指针的调整，在内循环改变一个节点ptr的位置后，外层循环的ptr的下一个循环就不是ptr->next了，而是pre->next

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head || !head->next) 
            return head;
        ListNode* ptr = head->next, *nex, *pre = head,*ptr2, *pre2,
        npre = ListNode(INT_MIN);
        npre.next = head;
        for( ; ptr != nullptr; ) {
            for(ptr2 = npre.next, pre2 = &npre; ptr2 != ptr; ptr2 = ptr2->next, pre2 = pre2->next){
                if(ptr2->val >= ptr->val) {
                    pre->next = ptr->next;
                    ptr->next = ptr2;
                    pre2->next = ptr;
                    break;
                }
            }
            if(ptr2 == ptr) {
                ptr = ptr->next;
                pre = pre->next;
            } else {
                ptr = pre->next;
            }
            // for(auto x = &npre; x != nullptr; x = x->next) {
            //     cout << x->val << " ";
            // }
            // cout << endl;
        }
        return npre.next;
    }
};

Accepted

22/22 cases passed (100 ms)

Your runtime beats 6.64 % of cpp submissions

Your memory usage beats 13.73 % of cpp submissions (9.7 MB)

🏆改进版

对于插入排序来说，我们没有必要记录那么多前置节点的位置，我们只要保证ptr左边的序列有序即可

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head || !head->next) 
            return head;
        ListNode* ptr = head, *nex,*ptr2, 
        npre = ListNode(INT_MIN);
        while(ptr) {
            nex = ptr->next;
            ptr2 = &npre;
            while(ptr2->next && ptr2->next->val < ptr->val)
                ptr2 = ptr2->next;
            ptr->next = ptr2->next;
            ptr2->next = ptr;
            // for(auto x = &npre; x != NULL; x = x->next) {
            //     cout << x->val << " ";
            // }
            // cout << " cur: " << ptr->val  << endl;
            ptr = nex;
        }
        return npre.next;
    }
};