Time Limit Exceeded.. but I don't see what's wrong with my code?


  • 0
    M

    Here's my solution. I keep getting Time Limit Exceeded error when the last expected input is an incredibly long array of numbers like Last executed input: {1,3,3,1,3,1,3,3,2,3,2,2,1,1,1,3,2,2,1,1,2,2,2,3,3,1,1,2,2,2,1,2,1,1,2,3,3,2,2,3,2,3,2,2,2,1,1,3,2,3,3,1,1,1,2,2,1,2,2,2,2,3,1,3,1,1,1,2,1,2,2,2,1,3,2,2,2,3,3,2,3,3,1,1,2,2,1,2,1,3,2,1,3,3,1,2,1,1,1,1,1,2,1,2,2,2,2,3,3,3,1,1,3,2,1,1,2,1,3,3,2,2,1,3,1,3,1,3,2,2,3,2,3,2,2,1,2,3,1,3,1,2,3,3,2,3,3,3,1,1,2,3,1,2,3,2,1,1,2,3,1,1,3,1,2,2,3,2,1,3,1,2,1,3,2,1,1,2,2,2,1,3,1,3,2,3,3,1,1,3,1,2,1,2,3,1,2,1,1,3,1,3,3,1,1,1,2,2,1,3,1,2,2,3,2,1,3,2,1,3,2,2,3,3,2,2,1,3,2,2,2,2,2,3,2,2,3,1,3,2,1,3,2,1,2,3,3,3,1,2,2,3,1,1,2,2,3,2,1,1,1,1,1,3,2,2,2,1,3,2,1,2,3,2,1,1,2,1,3,3,1,3,1,2,2,1,2,3,2,3,3,1,2,3,2,2,3,3,2,1,3,2,........ and it keeps going so much farther!

    Does anyone see what's wrong the code?

    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null){
                return;
            }
            if (head.next.next == null) //special case: list has 2 elements so just return 
            //need this or else i'll set the next of a node to itself, that's bad
            {
                return; 
            }
    
            ListNode nextNode = head.next;
            ListNode findEnd = head; 
            ListNode secondToLast = null;
            while (findEnd.next != null){
                if (findEnd.next.next  == null){
                    secondToLast = findEnd.next;    
                }
                //get to end
                findEnd = findEnd.next; 
            }
            //now findEnd is the last node
          
            findEnd.next = nextNode; //insert it at the front where it belongs
            head.next = findEnd; 
            
            //make sure that second to last one is now last so set next to null
            if (secondToLast != null){
                secondToLast.next = null; 
            }
            
            //recurse to switch whole list 
            if (nextNode.next != null){
            reorderList(nextNode.next);
            }
        }
            
            
        
    }

  • 0
    V

    Time complexity of above program is O(n^2) whereas the best possible time complexity is linear in n i.e., O(n). Program can be optimized to O(n) version by avoiding recursion and using linked list traversal to avoid TLE.

    class Solution {
    public:
         void reorderList(ListNode *head) {
            if(!head)
            return;
            if(head->next==NULL) return;
            ListNode* slow=head;
            ListNode* fast=head;
            //find middle
            while( fast && fast->next)
            {
                slow=slow->next;
                fast=fast->next->next;
            }
            //slow is mid.  reverse slow->next to end
            ListNode* current= slow->next;
            ListNode* prev= slow;
            while(current!=NULL)
            {
                ListNode *temp= current->next;
                current->next=prev;
                prev=current;
                current=temp;
            } 
            slow->next = NULL;
            ListNode* first= head;
            ListNode* second= prev;  
            while(first!=NULL  && second!=NULL && first!=second)
            {
                ListNode* temp=first->next;
                first->next=second;
                first = second;
                second = temp;
            }
        }
    };

  • 0
    Y

    why not using stack or deque. O(n) space complexity is not bad.


Log in to reply
 

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