New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

Intersection of Two Linked Lists

Contributed by

Arshit Babariya

Last Updated: 23 Feb, 2023

Easy

0/40

Avg time to solve 25 mins

Success Rate 73 %

139 upvotes

Problem Statement

Suggest Edit

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.

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.

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

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 9 1 2 -1
3 2 -1
4 -1

Sample Output 2 :

Sample Input 3 :

2 6 4 -1
1 5 -1
-1

Sample Output 3 :

-1

Auto

Console

LinkedLists Notes

Reverse List in K groups

Sum Between Zeroes

Rearrange Linked List

Clone Linked List with Random Pointer

Merge Two Sorted Linked Lists

Detect and Remove Cycle

Remove String

Add First and Second Half

Intersection of Linked List

Left Short

Count Inversion

Flatten The Multi-Level Linked List

Count triplets in a sorted doubly linked list whose sum is equal to a given value x

Deletion in Circular Linked List