GEtting time limit exceeded for large input


  • 0
    V
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            ListNode *ptrm = head;
            ListNode *ptr1=head;
            ListNode *last,*prevlast;
            if(ptrm!=NULL)
            {
            while(ptrm->next!=NULL && ptrm->next->next!=NULL)
            {
                ptr1=ptrm;
                while(ptr1->next!=NULL && ptr1->next->next!=NULL)
                {
                    ptr1=ptr1->next;
                }
                prevlast=ptr1;
                last=ptr1->next;
                last->next=ptrm->next;
                ptrm->next=last;
                prevlast->next=NULL;
                if(ptrm->next!=NULL)
                {
                ptrm=ptrm->next->next;
                }
                else
                {
                    ptrm=ptrm->next;
                }
                
            }
            }
        }
    };
    

    ERROR: Submission Result: Time Limit Exceeded

    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...}


  • 0
    S

    Hi vivek3, could you please describe your thought in some words and add some comment in your code? It will be helpful to others to find your error.


  • 0
    C

    I think your algorithm is not good enough. So it exceeds the time limit. Below is my solution.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(!head) return;
            vector<ListNode*> ln; // store listnode into vector
            ListNode *p=head;
            while(p!=NULL){
                ln.push_back(p);
                p=p->next;
            }
            int rear = ln.size()-1; // from end
            int front = 0;           // from begin
            while(front != rear && rear-front != 1){ // reorder
                ln[front]->next=ln[rear];
                ln[rear]->next=ln[front+1];
                front++; rear--;
            }
            ln[rear]->next = NULL;
        }
    };

Log in to reply
 

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