Find Merge node in 2 link lists | PROGRAMMING INTERVIEWS

Find Merge node in 2 link lists | PROGRAMMING INTERVIEWS

Question: There are 2 link lists merging at some node. Find the node, where these 2 lists merge.

1. Find length (len1) of first link list.
2. Find length (len2) of second link list.
3. find diff = abs(len1 – len2)
4. Traverse the bigger list from the first node till 'diff' nodes. Now we have two lists, which have equal no of nodes.
5. Traverse both the lists in parallel till we come across a common node.

1. struct node* findMergeNode(struct node* list1, struct node* list2)  
2. {  
3.   int len1, len2, diff;  
4.   struct node* head1 = list1;  
5.   struct node* head2 = list2;  
6.   
7.   len1 = getlength(head1);  
8.   len2 = getlength(head2);  
9.   diff = len1 - len2;  
10.   
11.   if (len1 < len2)  
12.   {  
13.       head1 = list2;  
14.       head2 = list1;  
15.       diff = len2 - len1;  
16.   }  
17.   
18.   for(int i = 0; i < diff; i++)  
19.       head1 = head1->next;  
20.   
21.   while(head1 !=  NULL && head2 != NULL)  
22.   {  
23.       if(head1 == head2)  
24.           return head1->data;  
25.       head1= head1->next;  
26.       head2= head2->next;  
27.   }  
28.   
29.   return NULL;  
30. }  

Read full article from Find Merge node in 2 link lists | PROGRAMMING INTERVIEWS