Two singly linked lists of integers with different number of elements and different start nodes merge after some nodes (possibly after different number of nodes from their respective heads) at a Y-junction. Return the data in the node at which they merge.

You need to write a function with signature "int FindMergePoint(Node *A,Node *B)". A and B will be pointers to the head of two linked lists.

Your function must return the value at first common node or the merge point.

We have been given two pointers to the Head of these two linked lists and We have to find and return the data of the position where these two linked lists got merged.

- Firstly,We will calculate the individual lengths of the linked lists.
- Lets assume,
**LenA**be the length of first list and**LenB**be the length of second list. - Also,lets assume for now
`lenA > lenB`

, So there are**(lenA - LenB)**more elements in first Linked List. - We can say that after only these much elements then after that starts some probablity at each position there might be a junction.
- So We'll get rid of these elements from First list by traversing these much positions.
- After that we'll traverse the two lists simultaneously and check the current addresses of both Linked lists if it's same or not. If we reach at that situation than the first occurence is our Junction and we'll immediately return the data at that position.

editorial written by ishabh

/* Find merge point of two linked lists Node is defined as struct Node { int data; Node* next; } */ int FindMergePoint(Node *HeadA,Node *HeadB) { // To store Lengths of Linked Lists int lenA = 0,lenB = 0; // Temporary Pointers to store address of nodes // To Be used in Traversal Node *traverse1,*traverse2; // Firstly Pointing them towards Heads traverse1 = HeadA; traverse2 = HeadB; // Calculating Length of First Linked List // Move till we reach End of Linked List while(traverse1) { // Moving Forward lenA ++; traverse1 = traverse1 -> next; } // Calculating Length of Second Linked List while(traverse2) { lenB ++; traverse2 = traverse2 -> next; } traverse1 = HeadA; traverse2 = HeadB; // Traversing the Extra Elements From The List if(lenA > lenB) { // To store Extra Elements int Extra = lenA - lenB; // Traversing Extra Elements while( Extra -- ) { traverse1 = traverse1 -> next; } } else if(lenA < lenB) { int Extra = lenB - lenA; while( Extra -- ) { traverse2 = traverse2 -> next; } } // Checking for a Junction /* If at some time the address of both the pointers gets Equal or becomes Same Then it is a Junction Only the First Meeting Point is a Junction */ while(traverse1 != traverse2) { // Traversing Both Lists Simultaneously traverse1 = traverse1 -> next; traverse2 = traverse2 -> next; } // Returning Data return traverse1 -> data; }

featured solution by ishabh