CareerCup

1. Find the length of 1st list says l1
2. Find the length of 2nd list says l2
3. Traverse the bigger list by (l1-l2) nodes from the beginning
4. From there, traverse both the lists in steps of 1 and check at each step if there is a merge by comparing the addresses of nodes
TC : O(m +n)

1. Find the length of 1st list says l1
2. Find the length of 2nd list says l2
3. Traverse the bigger list by (l1-l2) nodes from the beginning
4. From there, traverse both the lists in steps of 1 and check at each step if there is a merge by comparing the addresses of nodes
TC : O(m +n)

If two linked list merge their last or first node has to be same..
So here is the algo O(m+n)
1 Compare the first nodes of both lists if equal return true else go to step 2.
2 Traverse first list to get the last node (NON NULL)
3. Traverse second to get the last node (NON NULL)
4. compare the two nodes, if equal then lists are merged.

@AmzFAILFacebookFailMSFTFail, The question is to find the merging point of the two linked list? or just to check is the two linked list merge. For the former one, the solution from "manan" would suffice, else solution from "Sadasiva" is the right one.

p = head1 (bigger list); q = head2 (smaller list)
bool listMerge = false;
while(q!=null)
if(p->data== q->data) {
   p = p->next;
   q = q->next;
   listMerge = true;
}
else 
{
 // if this flag toggles then we found a mismatch hence return false
 // otherwise we have not yet found even the first node in the bigger list
 // which matched hence continue the traversal of bigger list
  if(listMerge == true)
     return false;
  else
     p = p->.next;
 }
 return true;

node *mergecheck(node *l1,node *l2)
{
 int len=0;
 node *p;
 for(p=l1;p!=NULL;p=p->next,len++)
  ;
 for(p=l2;p!=NULL;p=p->next,len--)
  ;
 for(;len>0;len--,l1=l1->next)
  ;
 for(;len<0;l2=l2->next)
  ;
 for(;l1!=l2;l1=l1->next,l2=l2->next)
  ;
 return l1;
}

How about using a hashmap here.
First list, parse the list and add to hashmap such that key=address of node and value=value of node.

For each of the second list elements' check if its address is already there in the hash table. If it is not available, then continue to the next element of the second linked list.

If at any point an entry is present in the hashtable=> Merge occurred.

Space Complexity O(m)
Time Complexity O(n).