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

**Answer:**We should have one fact in mind that merging node is found by comparing the address (not value) of the nodes. Since we have 2 different lists, one way is to have 2 for loops and compare addresses of all the possible nodes. This solution is O(mn) where 'm' and 'n' are lengths of given lists.

If length of 2 lists are of equal length, we can traverse both the lists one node at a time and find the common node. But since lengths may not be same, we first find a node in bigger list, from where we have length same as that of smaller list. For this, first we need to find the length of both the lists, then move ahead the difference in bigger list and then match nodes in parallel.

**Algorithm:**

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

**Code:**

struct node* findMergeNode(struct node* list1, struct node* list2)

{

int len1, len2, diff;

struct node* head1 = list1;

struct node* head2 = list2;

len1 = getlength(head1);

len2 = getlength(head2);

diff = len1 - len2;

if (len1 < len2)

{

head1 = list2;

head2 = list1;

diff = len2 - len1;

}

for(int i = 0; i < diff; i++)

head1 = head1->next;

while(head1 != NULL && head2 != NULL)

{

if(head1 == head2)

return head1->data;

head1= head1->next;

head2= head2->next;

}

return NULL;

}

**Complexity:**Complexity of above solution is O(m+n).

**PS:**Even if the lists don't merge at any intermediate point, they will always merge at NULL node in the end.

**PPS:**Try extending this solution to N lists, where N > 2.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
rajeevprasannaGood explanation.........

Similar question can be found here:

http://geeksforgeeks.org/?p=2405

Akash@Rajeev: Thanks Buddy, good link...

AnonymousWhat if the common point is in the distance you have moved ahead

First list

A B C D E F G H I J

Second list

K L C M N

Common point is C

Akash@Anonymous: The example, you given doesn't merge anywhere but at NULL (end). It seems that you are confusing with the question. Please read it carefully and relate with the diagram given. Also merging node is found by comparing the address (not value) of the nodes.

AnonymousIs it a good solution to convert this "Y" shaped set of linklist into a problem "find a loop in the linklist". We need to traverse a linklist and put a pointer from a the tail node to the head node. It will be a circular linklist.

Akash@Anonymous: Please note that loop might not be always result in circular list. It is possible that part of list is straight and part od f it has loop. I shall write a post to find loop in link list pretty soon.