Intersection Point in Y Shapped Linked Lists

PROBLEM :

There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the point where two linked lists merge.

Above diagram shows an example with two linked list having 15 as intersection point.

Expected time complexity is O(m + n) where m and n are lengths of two linked lists

Input:

You have to complete the method which takes two arguments as heads of two linked lists.


Output:
The function should return data value of a node where two linked lists merge.  If linked list do not merge at any point, then it shoudl return -1.

Constraints:
1 <=T<= 50
1 <=N<= 100
1 <=value<= 1000

Example:
Input:
2
2 3 2
10 20
30 40 50
5 10
2 3 0
10 20
30 40 50
First line is number of test cases. Every test case has four lines. First line of every test case contains three numbers, x (number of nodes before merge point in 1st list), y(number of nodes before merge point in 11nd list) and z (number of nodes after merge point).  Next three lines contain x, y and z values.

Output:
5
-1

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/* Link list Node
struct Node {
    int data;
    struct Node* next;
}; */


/* Should return data of intersection point of two linked
   lists head1 and head2.
   If there is no intersecting point, then return -1. */
 
int length(struct Node *) ;
int intersection(struct Node *,struct Node *,int ) ;
 
int intersectPoint(struct Node* head1, struct Node* head2)
{
    int l1,l2,d ;
    l1=length(head1) ;
    l2=length(head2) ;
    d=abs(l1-l2) ;
    if(l1>l2)
        d=intersection(head1,head2,d) ;
    else
        d=intersection(head2,head1,d) ;
       
    return d ;
}

int length(struct Node *head)
{
    struct Node *temp ;
    temp=head ;
    int l=0 ;
    while(temp!=NULL)
    {
        l++ ;
        temp=temp->next ;
    }
    return l ;
}

int intersection(struct Node *one,struct Node *two,int d)
{
    while(d!=0)
    {
        one=one->next ;
        d-- ;
    }
   
    while(one!=NULL&&two!=NULL)
    {
        if(one==two)
            return(one->data) ;
        else
        {
            one=one->next ;
            two=two->next ;
        }
    }
    return -1 ;
}

---------------------------------------------------------------------------------