Merge Point of Two Linked Lists

Moderate

0/80

10 upvotes

Asked in companies

Problem statement

Given two singly linked lists, 'FIRST_HEAD' and 'SECOND_HEAD'. Your task is to find the 'MERGING POINT' i.e. the data of the node at which merging starts. If there is no merging, return -1.

For example:-

The given Linked Lists are merging at node c1.
In this case, c1 is 'MERGING POINT'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The input format contains three lines consisting of three singly-linked lists. 

All three lines contain the elements of the singly linked list separated by a single space and terminated by -1.  

So first linked list would contain
       a1, a2, ...an, c1, -1. 

Similarly, the second line would contain
       b1,b2, ...bm, c1, -1. 

The third line would contain 
       c2, c3, ....ck, -1.


Refer 'a1, a2, ......, b1, b2, ......, c1, c2, ....., ck' from this image.

Output format :

The only line of output contains data of the first merged node's data. 
<b>If there is no merging output should contain -1. </b>

You don't have to explicitly print by yourself. It has been taken care of.

Constraints :

0 <= N <= 10^5     
0 <= M <= 10^5
0 <= K <= 10^5.
-10^9 <= data <= 10^9 and data != -1


 Time Limit: 1 sec

Sample Input 1 :

4 1 8 -1
5 6 1 8 -1
4 5 -1

Sample Output 1 :

Explanation For Sample Input 1:

As shown in the diagram the node with data is 8 at which merging starts

Sample Input 2 :

1 2 3 4 5 -1
2 3 4 5 -1
6 7 -1

Sample Output 2 :

Sample Input 3 :

2 6 4 -1
1 5 -1
-1

Sample Output 3 :

-1

Approaches (1)

Approach 1

App-1

Time Complexity

Space Complexity

(100% EXP penalty)

Merge Point of Two Linked Lists

Console