CareerCup

hash the second list.
O(n)

Just got a way in linear time with O(1) space complexity.
1. use two pointers scan the two list and get the size of each. say m, n (suppose m>n)
2. use the same two pointers point to the heads again and move the one in the longer list m-n steps.
3. move both of the two pointers step by step, compare their address in each step till find the same one.

Can plz explain in detail

Its o(n) coz we traverse the entire list !!

Its o(n) coz we traverse the entire list !!

o(n) time complexity question :)

sruct node *Intersection(struct node *l1,sruct node *l2)
{
int n=0,m=0;
struct node *temp1,*temp2;

if(l1==NULL || l2==NULL)
return NULL:
temp1=l1;
while(temp1)
{
n++;
temp1=temp1->next;
}
while(temp2)
{
m++;
temp2=temp2->next;
}
temp1=l1;
temp2=l2;
if(n>m)
{
temp1=l1;
n=n-m;
while(n)
{
temp=temp->next;
n--;
}
}
else
{
m=m-n;
temp2=l2;
while(m)
{
temp2=temp2->next;
m=m-1;
}}
while(temp1!=temp2)
{
temp1=temp1->next;
temp2=temp2->next;
}
return temp1;}