What's the problem with my C++ Quick Sort? Why time out?


  • 0
    K
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            if(head == NULL){
                return head;
            }
            
            ListNode* tail = head;
            while(tail->next != NULL){
                tail = tail->next;
            }
            
            head = _sortList(head, tail);
            return head;
        }
        
        ListNode *_sortList(ListNode* &head, ListNode* &tail){
            if(head == NULL){
                return head;
            }
            
            //fake headers for appending
            ListNode* small = new ListNode(0);
            ListNode* small_t = small;
            ListNode* big = new ListNode(0);
            ListNode* big_t = big;
            
            //devide
            for(ListNode* p = head->next; p != NULL;){
                ListNode* tmp = p;
                p = p->next;
                if(tmp->val < head->val){
                    small_t->next = tmp;
                    small_t = tmp;
                    tmp->next = NULL;
                }
                else{
                    big_t->next = tmp;
                    big_t = tmp;
                    tmp->next = NULL;
                }
            }
            
            //sort each side
            _sortList(big->next, big_t);
            _sortList(small->next, small_t);
            
            //link
            head->next = big->next;
            if(big_t != big){
                tail = big_t;
            }
            else{
                tail = head;
            }
            
            delete big;
            if(small->next != NULL){
                small_t->next = head;
                head = small->next;
            }
            delete small;
            
            return head;
        }
    };

  • 0
    T
     while(tail->next != NULL){
                tail = tail->next;
            }
    

    No need find the tail. Just use null as the tail.


  • 0
    C

    Quicksort is O(n^2) btw


Log in to reply
 

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