Why my program shows "Time Limit Exceeded" even for {1,2,3}


  • 0
    H

    Hello

    My code is using simple logic:
    1, reverse a linked list from middle node to last node;
    2, merge these 2 linked lists.
    I think the {1,2,3} case should return very early. I also tested my code using Dev-C++. The output is correct.

    Thanks.

    class Solution {

    public:

    ListNode *Reverse(ListNode *head){
    
        if (head->next != NULL){
            ListNode *retV = Reverse(head->next);
            retV->next = head;
            return head; // always return end of linkedlist
        }
        else{
            return head;
        }
    
    }
    
    void reorderList(ListNode *head) {
    
        if (head == NULL || head->next == NULL || head->next->next==NULL)
            return;
    
        if (head->next->next->next == NULL) {
            ListNode *n2 = head->next;
            ListNode *n3 = n2->next;
            head->next = n3;
            n3->next = n2;
            return;
        }
    
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *slowprev;
        int nodeCount = 0;
        while (slow != NULL){
            slow = slow->next;
            nodeCount ++; 
        }
        //Now we have nodeCount
        if (nodeCount%2 == 0){
            slow = head->next;
            fast = head->next;
        }
        else{
            slow = head;
            fast = head;
        }
        
        //now we get to the middle point
        while (fast->next != NULL) {
            slowprev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        //now we reverse. fast reaches end, we link from fast to slow
        slowprev->next = NULL;
        ListNode *reversedList = Reverse(slow);
        
        //Now we have 2 linked list, one from head, one from fast, we merge them.
        ListNode *node1 = head;
        ListNode *node2 = fast;
        ListNode *tmp;
        ListNode *n2prev;
        while (node1 != NULL && node2 !=NULL){
            n2prev = node2;
            tmp = node2->next;
            node2->next = node1->next;
            node1->next = node2;
            
            node1 = node2->next;
            node2 = tmp;
        }
        //now, it is possible node1 == NULL but node2 != NULL
        if (node2!=NULL)
            n2prev->next = node2;
            
        return;
    }
    

    };


Log in to reply
 

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