What's the problem of my quicksort code?


  • 0
    Y

    The result is Time Limit Exceed and the input is a huge array.

    class Solution {
    public:
    ListNode* sortList(ListNode* head) {
    if (head==NULL||head->next == NULL)
    return head;
    ListNode *dummy1 = new ListNode(0);
    ListNode *dummy2 = new ListNode(0);
    ListNode *temp1 = dummy1,*temp2 = dummy2;
    ListNode *key = head;
    head = head->next;
    while (head!=NULL)
    {
    if (head->val<=key->val)
    {
    temp1->next = head;
    temp1 = temp1->next;
    }
    else
    {
    temp2->next = head;
    temp2 = temp2->next;
    }
    head = head->next;
    }
    temp1->next = NULL;
    temp2->next = NULL;
    dummy1->next = sortList(dummy1->next);
    dummy2->next = sortList(dummy2->next);
    temp1 = dummy1;
    while (temp1->next !=NULL)
    temp1 = temp1->next;
    temp1->next = key;
    key->next = dummy2->next;
    return dummy1->next;
    }
    };


Log in to reply
 

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