C++ QuickSort 43ms beats 99.82%


  • 0
    A

    Considering recursive calls, the space complexity is actually O(logn), not O(1).
    Please share your thoughts

        // Quick Sort
        ListNode* sortList(ListNode* head) {
            
            if (!head || !head->next) {
                return head;
            }
            
            ListNode* l;    // left half
            ListNode* r;    // right half
            ListNode* m;    // pivot
            ListNode* lt;
            ListNode* rt;
            ListNode* mt;
            ListNode d1(0); // dummy
            ListNode d2(0);
            
            // choose pivot and divide
            l = &d1;
            r = &d2;
            m = head;
    
            // skip pivot
            head = head->next;
            lt = l;
            rt = r;
            mt = m;
            
            // divide
            while (head) {
                if (head->val < m->val) {
                    lt->next = head;
                    head = head->next;
                    lt = lt->next;
                } else if (head->val > m->val){
                    rt->next = head;
                    head = head->next;
                    rt = rt->next;
                } else {
                    mt->next = head;
                    head = head->next;
                    mt = mt->next;
                }
            }
            
            // handle tail
            lt->next = nullptr;
            rt->next = nullptr;
            mt->next = nullptr;
            
            // remove dummy
            l = l->next; 
            r = r->next;
            
            // recursive step
            l = sortList(l);
            r = sortList(r);
            
            // merge
            if (!l) {
                head = m;
                mt->next = r;
            } else {
                head = l;
                lt = l;
                while (lt->next) lt = lt->next; // find the tail of left half
                lt->next = m;
                mt->next = r;
            }
            return head;
        }
    

  • 0
    A

    Merge sort 59 ms:

        // Merge Sort
        ListNode* sortList(ListNode* head) {
            
            if (!head || !head->next) return head;
            
            ListNode* fast = head;
            ListNode* slow = head;
            ListNode* tail = head;
            
            while (fast && fast->next) {
                fast = fast->next->next;
                tail = slow;
                slow = slow->next;
            }
            
            tail->next = nullptr;
            ListNode* h1 = sortList(head);
            ListNode* h2 = sortList(slow);
            
            ListNode dummy(0);
            head = &dummy;
            while (h1 && h2) {
                if (h1->val < h2->val) {
                    head->next = h1;
                    head = head->next;
                    h1 = h1->next;
                } else {
                    head->next = h2;
                    head = head->next;
                    h2 = h2->next;
                }
            }
            if (!h1) head->next = h2;
            else head->next = h1;
            
            return dummy.next;
            
        }
    

Log in to reply
 

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