Modified version of ordinary quick sort to avoid TLE


  • 0
    E
    ListNode *sortList(ListNode *head) {
        return sort_helper(head, NULL);
    }
    
    // Slightly modified version of quick sort.
    ListNode *sort_helper(ListNode *head, ListNode *end) {
        if (head == NULL || head == end)
            return head;
    
        // The basic idea is that: 
        // all elements on the left side of i are less than pivot,
        // all elements in between (i, ii) equal to pivot,
        // all elements on the right side of ii are greater than pivot.
        ListNode *pi = NULL, *i, *j, *ii;
        int pivot = head->val;
        int ni = 0, nii = 0;
        for (i = j = ii = head->next; j != end;) {
            if (j->val < pivot) {
                if (i != j) {
                    swap(i->val, j->val);
                }
                pi = i;
                i = i->next;
                ++ni;
                if (ni > nii) {
                    ii = i;
                    nii = ni;
                }
            } else if (j->val == pivot) {
                if (ii != j) {
                    swap(ii->val, j->val);
                }
                ii = ii->next;
                ++nii;
            }
            j = j->next;
        }
        if (pi) {
            swap(pi->val, head->val);
    
            sort_helper(head, pi);
            sort_helper(ii, end);
        } else {
            sort_helper(ii, end);
        }
        return head;
    }

Log in to reply
 

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