Why Time Limit Exceeded?


  • 0
    7

    the first time use merge sort for list,but i think there is nothing wrong with :) why Time Limit Exceeded?

    class Solution {
    public:
        ListNode *mergeList(ListNode *head1,ListNode *head2)
        {
            ListNode *tmp,*p;
            if(!head1) return head2;
            if(!head2) return head1;
            if(head1->val < head2->val)
                tmp = head1,head1 = head1->next;
            else
                tmp = head2,head2 = head2->next;
            p = tmp;
            while(head1 && head2)
            {
                if(head1->val < head2->val)
                    tmp->next = head1,tmp = tmp->next,head1 = head1->next;
                else
                    tmp->next = head2,tmp = tmp->next,head2 = head2->next;
            }
            while(head1)
                tmp->next = head1,tmp = tmp->next,head1 = head1->next;
            while(head2)
                tmp->next = head2,tmp = tmp->next,head2 = head2->next;
            return p;
        }
        ListNode *sortList(ListNode *head)
        {
            if(!head) return NULL;
            ListNode *quick,*low,*ans;
            ans = quick = low = head;
            if(quick->next && quick->next->next)
            {
                quick = quick->next->next;
                low = low->next;
            }
            if(low->next == NULL) return ans;
            quick = low->next;
            low->next = NULL;
            low = head;
            ListNode* l = sortList(low);
            ListNode* q = sortList(quick);
            ans = mergeList(l,q);
            return ans;
        }
    };

  • 0

    Could you format your code by selecting your code, and clicking on the {} button? Please briefly describe your solution in a few sentences. Read the FAQ for guidelines on asking a question.


  • 0
    D

    in mergeList(), after looping head1 and head2, try simply assign the non-null one to tmp->next, instead of go through the list node by node.


  • 1
    A

    I got timeout error with quick sort implementation. I had to submit the solution a few more times to actually see OJ's input. It was like really really long array. I managed to copy it and executed the program on my single box. I got stack overflow :-).

    I guess, the solution is alright, its OJ that goes crazy in this case.


  • 1
    T

    if(quick->next && quick->next->next)

    I guess you want to do
    while (quick->next && quick->next->next)

    This should be the reason.


  • 0
    7

    true,do while(quick->next && quick->next->next). get accepted:)


  • 0
    7

    :) thank you for believe my solution


Log in to reply
 

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