56ms C++ Solutions using Quicksort with Explanations


  • 18

    There are many merge-sort solutions at the forum, but very few quicksort solutions. So I post my accepted quicksort solution here.

    Well, after reading the problem statement, I intuitively select quicksort since it is able to give an in-place solution and thus costs only constant space. Also, it is O(nlogn) in the expected case though it may become O(n^2) in the worst case.

    Then I implement my quicksort solution and test it. I then submit it to the online judge. However, the annoying TLE error occurred. I check for the forums and some people suggested to use random pivoting or duplicate skipping. However, implementing random pivoting is a little costly, I lazily tried to skip the duplicates. And it works! So now comes the following solution . Note that each time I choose the first node as the pivot. Moreover, I create a new_head that points to head for convenience.

    Of course, this solution passes the online judge luckily. If the linked list is like: 100000 -> 99999 -> 99998 -> ... -> 1, it will fail since the subproblems only decrease by 1 at each recursion. However, it seems that the LeetCode OJ does not have this kind of test cases.

        void sortListHelper(ListNode* head, ListNode* tail) {
        	if (head -> next == tail) return;
        	/* Partition the list. */
        	ListNode* pre = head;
        	ListNode* cur = head -> next; 
        	ListNode* pivot = cur;
        	while (cur -> next && cur -> next != tail) {		
        		if (pivot -> val > cur -> next -> val) {
        			ListNode* temp = pre -> next;
        			pre -> next = cur -> next;
        			cur -> next = cur -> next -> next;
        			pre -> next -> next = temp;
        		}
        		else cur = cur -> next;
        	}
        	sortListHelper(head, pivot);
        	/* Here is the trick. */
        	while (pivot -> next != tail && pivot -> next -> val == pivot -> val)
        	    pivot = pivot -> next;
        	if (pivot -> next != tail) sortListHelper(pivot, tail);
        } 
        
        ListNode* sortList(ListNode* head) {
        	ListNode* new_head = new ListNode(0);
        	new_head -> next = head;
        	sortListHelper(new_head, NULL);
        	return new_head -> next;
        }

  • 0
    S

    why skip dupiicate get rid of TLE?this means seem to be work on this test case?


  • 0

    Well, this is simply a trick. Possibly the test cases contain a lot of duplicates and cause TLE if we do not skip them. In fact, I am also very curious :)


  • 2
    C

    I believe it does not use constant space.


  • 0

    Hi, arindamkhaled. Thank you for your remind. I forget to consider the space of the function call stack.


Log in to reply
 

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