Is there method better than O(n^2)?


  • 0
    M

    I implement the solution by regular insert sort (in time of O(n^2)), but it cant be accepted due to TLE. I'm wondering if there is better time consuming insert sort?

    Here is my code. I think it's very intuitive. I track the original list by "it", and compare it to all sorted elements which is iterated by "cmp". To implement insertion, I also maintain a pointer "precmp" to hold the position for insertion.

    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            if(!head) return 0;
            ListNode * dummy=new ListNode(-65535);
            dummy->next=head;
            head=dummy;
            ListNode *it=head;
            ListNode *cmp=head;
            while(it->next!=NULL){
                ListNode *pre=it;
                it=it->next;
    
                ListNode *precmp=head;
                cmp=head->next;
                while(cmp!=it && cmp->val <= it->val){
                    precmp=cmp;
                    cmp=cmp->next;
                }
                if(cmp!=it){
                    pre->next=it->next;
                    precmp->next=it;
                    it->next=cmp;
                }
            }
            return dummy->next;
        }
    };

  • 6
    F

    Hi, mcrystal. I don't think the TLE is due to the O(n^2) time complexity. I originally have the same problem as yours. I believe you accidentally produced a circular list in your program. You can do a quick check by generating a two-node list, sorting it, and printing out the results. The way I dealt with it is: once you get the iterator for the rest of the original list, break the list into two parts--- one is the sorted one, the other is the rest part of the original list. This will surely prevent your program from generating circular list. Good luck!


  • 0
    Y

    I got the TLE too with a large input. First thing I realized is that the input list is sorted or almost sorted ( am not sure if it is fully sorted. It is a large list. Maybe I should note it down and write a simple code to check it is fully sorted). On the other hand the problem is asking for an insertion sort, which by its theory is O(n^2). But O(n^2) is just about the running time's upper limit. So for this (almost) sorted list, I kept track of head and tail of the sorted portion while sorting it, and compare the next node first with the head and tail first (actually only tail is good enough for this case) This change passed the TLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.