Why my qsort method exceeds time limit?


  • 0
    M
    class Solution {
    public:
        ListNode *qsortList(ListNode *head, ListNode *tail) {
            if (head == tail)
                return head;
            
            ListNode *pivot = head;
            ListNode *p = head;
            ListNode *q = p->next;
            ListNode *ltail = NULL;
            
            while (q && q != tail->next) {
                if (q->val < pivot->val) {
                    p->next = q->next;
                    q->next = head;
                    head = q;
                    q = p->next;
                
                    //set tail of left side.
                    if (! ltail) {
                        ltail = head;
                    }
                }
                else {
                    p = p->next;
                    q = q->next;
                }
            }
            
    		tail = p;
    
            if (head != pivot) {
                //Left side needs recursion.
                head = qsortList(head, ltail);
            }
            
            if (pivot != tail) {
                //Right side needs recursion.
                pivot->next = qsortList(pivot->next, tail);
            }
            
            return head;
        }
        
        ListNode *sortList(ListNode *head) {
            if (! head)
                return NULL;
            
            ListNode *tail = head;
            
            while (tail->next) {
                tail = tail->next;
            }
            
            return qsortList(head, tail);
        }
    };
    

    The time complexity should be in nlogn. Why it exceeds the time limits?


Log in to reply
 

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