simple C++ quicksort


  • 0
    B
    ListNode *sortList(ListNode *head, ListNode **newEnd = nullptr) {
        if (!head or !head->next) return head;
        ListNode left(-1), right(-2), *leftCurrent(&left), *rightCurrent(&right), *cur(head->next), *midCurrent(head);
        int pivotVal = head->val;
        while (cur) {
            auto next = cur->next;
            if (pivotVal == cur->val) {
                midCurrent = midCurrent->next = cur;
            } else if (cur->val < pivotVal) {
                leftCurrent = leftCurrent->next = cur;
            } else {
                rightCurrent = rightCurrent->next = cur;
            }
            cur = next;
        }
        leftCurrent->next = nullptr;
        left.next = sortList(left.next, &leftCurrent);
        rightCurrent->next = nullptr;
        right.next = sortList(right.next, &rightCurrent);
        leftCurrent->next = head;
        midCurrent->next = right.next;
        if (newEnd)
            *newEnd = &right != rightCurrent ? rightCurrent : midCurrent;
        return left.next ? left.next : head;
    }
    
    

Log in to reply
 

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