Memory Limited Exceeded, Please Help


  • 0
    J

    Hello, my method is to make an array to store all the starting address, and then if in the array, there is identical value, then return true, believe there is a circle.
    But it gives me Memory Limited Exceeded error, and I don't know where is the problem, could anyone please help?

        class Solution {
    public:
        bool hasCycle(ListNode *head) {        
            vector<ListNode*> start; //store the starting address
            ListNode* tmp = head;
            
            if(head==NULL)
                return false;
                
            while(tmp!= NULL){
                start.push_back(tmp);
                tmp = tmp->next;
            }//finish copying all the starting address to vector start
            
            for(int i = 0; i< start.size()-1;i++){
                for(int j = i+1; j< start.size();j++){
                    if(start[i]==start[j]){
                        return true;
                    }
                }
            }
            return false;
        }
    };

  • 0
    J

    I know the error now, as if there is a circle, it's impossible to stop the while loop which is used to copy the address.
    Thanks anyway:)


  • 0
    M

    glad you could find your error Jenna. but clearly your solution is using O(n) memory. also those two for loops are super costly.
    here is another solution that might help you.
    this method is called Floyd’s Cycle-Finding Algorithm. this is also considered the fastest method. what you precisely do is take two pointers, one that is incremented once, and another that is incremented twice. lets name them slow_ptr and fast_ptr. Suppose we have a linked list like 1->2->3->4->2 where the last 2 actually means that 4 is looping back to the 2 at first index. now the slow_ptr will move as follows : 1->2->3->4 and the fast_ptr will move as : 1->3->2->4.
    at this point, they both point to the same node, and hence we can return true. if at any point we find a null, we can simply return false.
    here is my code to make things more clear.
    p.s. : this solution took 52 ms.
    please do let me know if there could be more improvements.

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *slow_ptr = head, *fast_ptr = head;
            while(slow_ptr != NULL && fast_ptr != NULL && fast_ptr->next != NULL)
            {
              slow_ptr = slow_ptr->next;
              fast_ptr = fast_ptr->next->next;
              if(slow_ptr == fast_ptr)
                return true;
            }
            return false;
        }
    };  

Log in to reply
 

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