Who can tell me what's the problem with my mergesort, it's TLE.


  • 0
    W

    class Solution {// Time Limit Exceeded why??
    public:

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode *head;
    ListNode *rear;
    ListNode *p1;
    ListNode *p2;

        p1 = l1;
        p2 = l2;
        rear = NULL;
        if ( l1 == NULL)   
            return l2;
        if ( l2 == NULL )
            return l1;
        if ( p1->val < p2->val )
        {
            rear = p1;
            p1 = p1->next;
        }
        else
        {
            rear = p2;
            p2 = p2->next; 
        }
        head = rear;
        while ( p1 != NULL && p2 != NULL )
        {
            if ( p1->val < p2->val )
            {
                rear->next = p1;
                rear = p1;
                p1 = p1->next;
            }
            else
            {
                rear->next = p2;
                rear = p2;
                p2 = p2->next;
            }
        }
        if ( p1 == NULL )
            rear->next = p2;
        if ( p2 == NULL )
            rear->next = p1;
        return head;
    }
    
    ListNode *MergeSort( ListNode *L1 )
    {
        if ( L1 == NULL || L1->next == NULL )
            return L1;
        else
        {
            ListNode *lower = L1;
            ListNode *faster = L1->next;
            if ( faster != NULL && faster->next != NULL )
            {
                lower = lower->next;
                faster = faster->next->next;
            }
            faster = lower->next;
            lower->next = NULL;
            ListNode* low1 = MergeSort( L1 );
            ListNode* low2 = MergeSort( faster );
            ListNode *newlist = mergeTwoLists( low1, low2 );
            return newlist;
        }
    }
    ListNode *sortList(ListNode *head) {    //Merge
        if ( head == NULL || head->next == NULL )
            return head;
        ListNode* newhead = MergeSort( head );
        return newhead;
    }
    

    };


Log in to reply
 

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