[Three-way Quick Sort] C++ beats 96%


  • 0
    H
    class Solution {
    private:
        pair<ListNode*, ListNode*> sortList(ListNode* head, ListNode* tail) {
            if (head == tail) return make_pair(head, head);
            int val = head->val;
            
            ListNode *it = head->next, *nexit = nullptr;
            ListNode *lessit = nullptr, *equalit = head, *moreit = nullptr;
            ListNode *lesshead = nullptr, *equalhead = head, *morehead = nullptr;
            
            while (it != tail->next) {
                nexit = it->next;
                if (it->val == val) {
                    equalit->next = it;
                    equalit = equalit->next;
                } else if (it->val < val) {
                    if (!lessit) {
                        lessit = it;
                        lesshead = it;
                    } else {
                        lessit->next = it;
                        lessit = lessit->next;
                    }
                } else {
                    if (!moreit) {
                        moreit = it;
                        morehead = it;
                    } else {
                        moreit->next = it;
                        moreit = moreit->next;
                    }
                }
                it = nexit;
            }
            
            equalit->next = nullptr;
            pair<ListNode*, ListNode*> upperhalf, lowerhalf, res;
            
            res.first = equalhead;
            res.second = equalit;
            if (lesshead) { 
                lessit->next = nullptr;
                upperhalf = sortList(lesshead, lessit);
                res.first = upperhalf.first;
                upperhalf.second->next = equalhead;
            }
            if (morehead) {
                moreit->next = nullptr;
                lowerhalf = sortList(morehead, moreit);
                res.second = lowerhalf.second;
                equalit->next = lowerhalf.first;
            }
            return res;
        }
    
    public:
        ListNode* sortList(ListNode* head) {
            if (!head) return head;
            ListNode *tail = head;
            while (tail->next) tail = tail->next;
            
            pair<ListNode*, ListNode*> range = sortList(head, tail);
            return range.first;
        }
    };
    

  • 0
    A

    @HaoxiangXu I wonder why nobody actually reads the description of the problem. It clearly says "constant space complexity". Recursive is definitely not.


Log in to reply
 

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