There are two singly linked lists in a system. By some programming error, the end node of one of the linked list got linked to the second list, forming an inverted Y shaped list. Write a program to get the point where two linked list merge.
You are given two Singly Linked List of integers, which are merging at some node of a third linked list.

Your task is to find the data of the node at which merging starts. If there is no merging, return -1.

For example:-

The given Linked Lists, where a1, a2, c1 is the first linked list, b1, b2, b3, c1 is the second linked list, and c1, c2, c3 is the third linked list which are merging at node c1.

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.

Output format :

The only line of output contains data of the first merged node. If there is no merging output should contain -1. You don't have to explicitly print by yourself. It has been taken care of.

Constraints :

0

Question

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

You are given two Singly Linked List of integers, which are merging at some node of a third linked list.

Your task is to find the data of the node at which merging starts. If there is no merging, return -1.

For example:-

The given Linked Lists, where a1, a2, c1 is the first linked list, b1, b2, b3, c1 is the second linked list, and c1, c2, c3 is the third linked list which are merging at node c1.

alt.txt

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.

Output format :

The only line of output contains data of the first merged node. If there is no merging output should contain -1.

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

Accepted Answer

Simple approach - Use 2 nested loops. The outer loop will be for each node of the 1st list and inner loop will be for 2nd list.
Optimised Approach -
Get count of the nodes in the first list, let count be c1.
Get count of the nodes in the second list, let count be c2.
Get the difference of counts d = abs(c1 – c2)
Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

Accepted Answer

Brute Force

For each node in the first list, traverse the entire second list
Check if any node in the second list coincides with the first list
- If it does, return that node’s data
- If it doesn’t, return -1

Space Complexity: O(1)Explanation:

O(1)

Since we only use constant space.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M are the lengths of the first and second linked lists respectively.

Since, for each element of the first list, we are traversing for the second list, therefore the time complexity is O(N * M)

Accepted Answer

Hashing Approach

Traverse the first list and store the address/reference to each node in a hash set/map/dictionary.
Then check every node in the second list:
- If the address of the node of the second list appears in the hash set/map/dictionary, then the node is the intersection node
- If we do not find any address of the second list node in the hash set/map/dictionary then return -1

Space Complexity: O(n)Explanation:

O(N) or O(M), where N and M are the lengths of the first and second linked lists respectively.

Since we are storing nodes in the hash set, depending on which list’s nodes you store in the hash set/map/dictionary.

Time Complexity: OtherExplanation:

O(N+M), where N and M are the lengths of the first and second linked lists respectively.

Since we are traversing on the first and second linked list separately.

Accepted Answer

Parallel Traversal Approach

Calculate the length of both the lists, say len1 and len2
Get the absolute difference of the lengths, diff = |len1 – len2|
Now traverse the long list from the first node till ‘diff’ nodes so that from there onwards both the lists have equal number of nodes
Then traverse both the lists in parallel and check whether a common node is reached (Note that getting a common node is done by comparing the address of the nodes, not the data)
- If yes, return that node’s data
- If no, return -1

Space Complexity: O(1)Explanation:

O(1)

Since we only use constant space.

Time Complexity: O(n)Explanation:

O(N), where N is the maximum length of the linked list.

Since we have to traverse only the longer linked list, therefore, the time complexity is O(N).