3 ways quicksort, O(1) sapce, cpp solution.


  • 1
    I

    The idea is quite simple. use head to do 3 ways partition. Then sort the small part and the large part and merge.

    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            if(head == NULL || head->next == NULL){
                return head;
            }
            int base = head->val;
            ListNode *dummy_small = new ListNode(0);
            ListNode *dummy_mid = new ListNode(0);
            ListNode *dummy_large = new ListNode(0);
            ListNode *pt[3]; // pt0 small, pt1 equal ,pt2 large
            pt[0] = dummy_small;
            pt[1] = dummy_mid;
            pt[2] = dummy_large;
            ListNode *p = head;
            while(p != NULL){
                int idx = 1;
                if(p->val < base){
                    idx = 0;
                }else if (p->val > base){
                    idx = 2;
                }
                pt[idx]->next = p;
                p = p->next;
                pt[idx] = pt[idx]->next;
                pt[idx]->next = NULL;
            }
            ListNode* head_small = sortList(dummy_small->next);
            ListNode* head_large = sortList(dummy_large->next);
            // mid to large
            pt[1]->next = head_large;
            if(head_small == NULL){
                return dummy_mid->next;
            }else{
                p = head_small;
                while(p->next != NULL){
                    p = p->next;
                }
                p->next = dummy_mid->next;
                return head_small;
            }
            
        }
    };

  • 1
    S

    Your three pointer array is great! But I think the recursive call needs a O(n) stack. So it's not O(1). Maybe put an outer loop to do quick sort on n, n/2, n/4 ... scale.


  • 0
    X

    I agree with siyang3.


Log in to reply
 

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