## Merge point of two linked lists

Given two linked lists, we need to find out that if two linked lists merge, if yes, find the merge point.

For example, in the figure below, node(5) is the merge point of two linked lists.

How can we identify that two linked lists do not merge? Easy, if two linked lists merge at any given node including the last node, the last node should be the same. If the last nodes of two linked lists are different, we can safely say that two linked lists do not merge.

### Merge point of two linked lists

How to find the merge point is the next problem. From the above diagram, notice that all the nodes after the merge point are the same if two linked lists are merged at a certain node. So that part of two linked lists is common to both.

We can use this insight to find the merge point. If lengths of two linked lists are equal, then we can just start traversal of those lists from heads and they will meet the merge point.

What if the lengths are different? In this case, there is an equal number of nodes in two linked list after the merge point. The difference has to be before the merge point. If we get the difference between the lengths and move the pointer on the longer list head by the difference, we will reach the merge point at the same time when we traverse lists again.

If the length of two linked lists is different, the problem reduces to the problem where we need to reach the end of two lists at the same time. There is a simple solution to that.

#### Implementation

#include<stdlib.h> #include<stdio.h> typedef struct node{ int data; struct node *next; } Node; void print_list(Node * head){ while(head){ printf("%d->" , head->data ); head = head->next; } printf("NULL"); printf("\n"); } int merge_point(Node *L1, Node *L2){ Node * current1 = L1; Node * current2 = L2; int count_1 = 0; int count_2 = 0; //If any one list is null, return false if(!current1 || !current2 ) return -1; //Count number of nodes in list 1; while(current1->next){ count_1++; current1 = current1->next; } // Count number of nodes in list 2 while(current2->next){ count_2++; current2 = current2->next; } /*If last nodes of both linked list are not same, linked list don't merge. */ if(current1 != current2) return -1; //Calculate the difference in lengths of linked list. int diff = abs(count_1 - count_2); //Move the longer linked list by diff number of nodes if(count_1 < count_2){ Node * temp = L1; L1 = L2; L2 = temp; } current1 = L1; current2 = L2; while(diff && current1){ diff--; current1 = current1->next; } // Now move both linked list till they meet at merge point while(current1 != current2){ current1 = current1->next; current2 = current2->next; } return current1->data; } void push(Node **head, int value){ if(*head == NULL){ (*head) = (Node *)malloc(sizeof(Node)); (*head)->data = value; (*head)->next = NULL; } else{ Node * newNode= (Node *)malloc(sizeof(Node)); if(newNode){ newNode->data = value; newNode->next = (*head); *head = newNode; } } } void main(){ Node * L1 = NULL; Node * L2 = NULL; push(&L1,3); Node * temp1 = L1; push(&L1,4); push(&L1,6); push(&L1,7); push(&L1,8); push(&L1,9); print_list(L1); printf("\n"); push(&L2,5); Node * temp2 = L2; push(&L2,7); push(&L2,8); push(&L2,2); push(&L2,1); push(&L2,10); printf("\n"); temp2->next = temp1; print_list(L2); int result1 = merge_point(L1, L2); if(result1 != -1){ printf("\n Merge Point : %d", result1); } else{ printf("\n Lists don't merge"); } }

The complexity of the algorithm to find merge point of two linked list is `O(n)`

, however, we scan the lists multiple times.

Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching, please signup for a free demo session.