Best solution for this problem


#1

ListNode* Solution::getIntersectionNode(ListNode* A, ListNode* B)
{
while(A != NULL && B != NULL)
{
if(A == B)
return A;
A = A->next;
B = B->next;
}
}


#2

I would suggest you actually try this.


#3

Hello Sir,
I would like to know how what will the program return if they do not have the same length?
when i simulated your code in pen paper what i felt is it didn’t determine for those not of same length. Am i right?


#4

I know you are responding to someone else, but you are correct – the solution the commenter gave will not work when the lists are different lengths. It helps to get a clear definition of what the intersection point is. Then figuring out what to do in the case where the lists are different lengths is pretty simple. I’ll give you a hint. Suppose you have two strands of rope that eventually twine together to form a single rope. The ropes are different lengths. You have no idea where the ropes meet because for some reason you can’t see it. But you know where each of the strands start and you know that it will be easier to find the middle if you move down each strand at the same time. What do you do with the longer strand to make sure that you can move down each strand at the same time?


#5

For these test cases , this code works , but it doesn’t work all the time. Take a to be very long list and B to be a short list intersecting A at the end. By the time B crosses the intersection point , A might be at the start. Then if(A==B) will occur at the tail but intersection may be in the front.


#6

Your code will not work when both have different length, So first of all we need to cut the extra length. You can check below :

ListNode* Solution::getIntersectionNode(ListNode* A, ListNode* B) {

int c1=0, c2=0;

ListNode* svar = A;

while( svar != NULL ){
    
    ++c1;
    svar = svar->next;
}

svar = B;

while( svar != NULL ){
    
    ++c2;
    svar = svar->next;
}

ListNode* s1 = A;
ListNode* s2 = B;

if( c1>c2 ){
    
    c1 = c1-c2;
    
    while( c1>0 ){
        
        s1 = s1->next;
        --c1;
    }
}
else{
    
    c2 = c2-c1;
    
    while( c2>0 ){
        
        s2 = s2->next;
        --c2;
    }
}

while ( s1 != s2 ){
    
    s1 = s1->next;
    s2 = s2->next;
}

if( s1 != s2 )
    return NULL;

return s1;

}


#7

Life Saver Video, I was able to solve the problem in 5 minutes with O(n+m) complexity

Thank you.Highly recommended to all my friends.