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