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.
InputYou 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.
OutputYour 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.
lenA > lenB
,
So there are (lenA - LenB) more elements in first Linked List.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