Why is my code time limit exceeded?


  • 0
    L

    my solution is using the quick-sort, why is it time limit exceeded?

    class Solution {
    public:
        void sortIt(ListNode* head, ListNode* end){
            if (head == NULL || head->next == NULL) return ;
            if(head == end) return;
            ListNode *p = head;
            ListNode *q = head->next;
            int val = head->val;
            while(q && q != end) {
                if(q->val < val) {
                    p->val = q->val;
                    q->val = p->next->val;
                    p = p->next;
                }
                q= q->next;
            }
            p->val = val;
            sortIt(head,p);
            sortIt(p->next, q);
        }
        ListNode* sortList(ListNode* head) {
            if(head == NULL || head->next == NULL) return head;
            sortIt(head, NULL);
            return head;
        }
    };

  • 0
    J

    quick sort is not O(n logn ) , it will ne O(n^2) in the worst case.


Log in to reply
 

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