Problem

Submissions

Hints & solutions

Discuss

Intersection of Two Linked Lists

Easy

0/40

Average time to solve is 25m

Contributed by

304 upvotes

Asked in companies

Problem statement

You are given two Singly Linked Lists of integers, which may have an intersection point.

Your task is to return the first intersection node. If there is no intersection, return NULL.

Example:-

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

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

Input Format:

The input format contains three lines consisting of the front part of the first list, front part of the second list and the intersection part of the lists, respectively.

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

So the first line would contain
       a1, a2, ...an, -1. 

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

Similarly, the third line would contain
       c1, c2, ...ck -1.

Output format :

The only output line contains data from the first merged node if the correct node is returned. If there is no merging or incorrect answer, the output contains -1.

You don't have to print by yourself explicitly. It has been taken care of. You need to return the first merged node.

Sample Input 1 :

4 1 -1
5 6 -1
8 -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 -1
3 -1
2 -1

Sample Output 2 :

Constraints :

-10^9 <= data <= 10^9 and data != -1
 The length of both the linked list is positive.
 Time Limit: 1 sec

Hint 1

Hint 2

Hint 3

Two nested loops?

Approaches (3)

Approach 1

Approach 2

Approach 3

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
- If it doesn’t, return NULL

Time Complexity

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)

Space Complexity

O(1)

Since we only use constant space.

(75% EXP penalty)

(100% EXP penalty)

Intersection of Two Linked Lists

Console