Using 3-way quick sort


  • 1
    Z
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode lh(0), rh(0), mh(0);
        ListNode *lt = &lh, *rt = &rh, *mt = &mh;
        int val = head->val;
        while (head != NULL) {
            if (val > head->val) {
                lt->next = head;
                lt = head;
            } else if(val == head->val) {
                mt->next = head;
                mt = head;
            } else {
                rt->next = head;
                rt = head;
            }
            head = head->next;
        }
        lt->next = rt->next = NULL;
        lh.next = sortList(lh.next);
        rh.next = sortList(rh.next);
    
        lt = &lh;
        while (lt->next)
            lt = lt->next;
        lt->next = mh.next;
        mt->next = rh.next;
        return lh.next;
    }

Log in to reply
 

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