Memory Limit Exceeded - Please Explain.


  • 0
    R

    Please find my solution below.
    In this implementation , I find the difference between the lengths of the lists and traverse the longer list by the difference . Now that we have same no. of elements in both the lists to be traversed. I traverse them one by one and check if the objects are equal . If so, I return the object which basically is the intersection point . Else, I return null.

    I am getting a Memory Limit Exceeded error. Please help me understand.
    I am new to JAVA, and would really appreciate your help.

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            
            if(headA==null || headB==null)
            {
                return null;
            }
            
            ListNode node_A = headA;
            ListNode node_B = headB;
            ListNode node_t=null;
            int countA=0;
            int countB=0;
            int diff=0,i=0;
            while(node_A!=null)
            {
                node_A = node_A.next;
                countA++;
            }
            while(node_B!=null)
            {
                node_B = node_B.next;
                countB++;
            }
            diff = countA-countB;
            if(diff<0)  //ListB is bigger
            {
              diff*=-1;
              node_B=headB;
              
              //traverse extra nodes in List B
              while(i<diff)
              {
                  node_B = node_B.next;
                  i++;
              }
              node_A = headA;
              while((node_A != null)|| ( node_B != null))
              {
                 if(node_A == node_B)
                    return node_A;
                 node_A = node_A.next;
                 node_B = node_B.next;
              }
            }
            else //ListA is bigger or equal to B
            {
              
              node_A=headA;
              
              //traverse extra nodes in list A
              while(i<diff)
              {
                  node_A = node_A.next;
                  i++;
              }
              node_B = headB;
              
              while((node_B != null ) || (node_A != null))
              {
                 if(node_B == node_A)
                    return node_B;
                 node_A = node_A.next;
                 node_B = node_B.next;
              }
            }
            
            return null;
        }
    }
    

    Thanks ,


  • 0
    B

    Well one issue I see is that if the two lists had no intersection, you have memory corruption in the while loops where you are tracing both lists. For example, what happens if node_A != null, but node_B == null?
    You will still enter the following while loop, and try to access node_B.next.

    while((node_A != null)|| ( node_B != null))
              {
                 if(node_A == node_B)
                    return node_A;
                 node_A = node_A.next;
                 node_B = node_B.next;
              }

  • 0
    R

    Thanks bigOh.
    That is exactly where the problem lies. Now, I used && instead of || and it works fine.


Log in to reply
 

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