Part 24 of 26 in Linked List - set 02

## Linked Lists merging at a Y-junction by animeshn

Problem statement

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.

Input

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.

Output

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;
}
*/
{
// 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

// 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;
}

// 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