Is merged sort the only solution?


  • 1
    M

    I've implemented quick sort at first, but it failed in the worst scenario and got a TLE. I guess that means it reaches the O(n^2).

    Then I checked the cheat sheet and implemented merged sort, it passed like a charm.

    I've also checked heap sort, it works best with an array, but in this case it's linked list here, so the space complexity will definitely not be O(1).

    So, any better solution?

    Code here:

    ListNode *quickSort(ListNode *head, ListNode *fin) {
    
        if (head == fin) {
            return head;
        }
    
        ListNode *left  = head;
        ListNode *right = head;
        ListNode *next  = NULL;
        ListNode *cur   = NULL;
    
        for (cur = head->next; cur != fin; cur = next) {
    
            next = cur->next;
    
            if (cur->val < head->val) {
                cur->next = left;
                left = cur;
            }
            else {
                right->next = cur;
                right = cur;
            }
        }
    
        /* right->next = fin; */
        head->next = quickSort(head->next, fin);
        return quickSort(left, head);;
    }
    
    ListNode *sortList(ListNode *head) {
        return quickSort(head, NULL);
    }

  • 1
    S

    I would say that quick sort should work as well. As far as I known, there is a way to avoid O(N^2) by selecting an random item in its process. Would you mind update your post with TLE quick sort solution?


  • 0
    M

    Hi, please check my updated post with the code.


  • 0
    L

    I think we need not only randomly pick the pivot in O(n) but also handle the case where all nodes' values are same in O(n).


Log in to reply
 

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