Intersection of Linked Lists

Easy
0/40
Average time to solve is 20m
profile
Contributed by
17 upvotes
Asked in companies
MakeMyTripCIS - Cyber InfrastructureMathworks

Problem statement

You are given two linked lists L1 and L2 which are sorted in ascending order. You have to make a linked list with the elements which are present in both the linked lists and are present in ascending order.

Example:- 
L1 = 1->2->3->4->7
L2 = 2->4->6->7

ANSWER:- The answer should be 2->4->7 because 2,4, and 7 are present in both the linked lists.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains the nodes of the first linked list. The line ends with -1 to indicate that the linked list is over.

The next line of every test case contains the head of the second linked list. The line ends with -1 to indicate that the linked list is over.
Output Format : 
For each test case, return the head of the intersecting linked list. If the intersecting linked list is empty, return NULL (denoted by -1).

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= Length of the the two linked lists <= 10^5 

Time Limit = 1 sec
Sample Input 1 :
2
1 3 5 -1
1 2 4 -1
2 3 -1
2 3 4 -1
Sample Output 1 :
1 -1
2 3 -1
Explanation for Sample Output 1 :
In the first test case, the intersecting linked list is 1, so the node containing 1 is returned.

In the second test case, the intersecting linked list is 2->3, so the node containing 2 is returned.
Sample Input 2 :
1
2 3 4 -1
1 5 6 -1
Sample Output 2 :
-1
Hint

Make proceedings in the linked list where the current element is smaller.

Approaches (1)
Greedy

If the current element in the first element is equal to the current element in the second linked list add that element to the final linkedlist. Else, if the current element in the first linked list is smaller, iterate to the next element in the first linked list , otherwise iterate to the next element in the second linked list. We stop when we reach the end of 1 linked list.

 

Algorithm:-

 

  1. Initialize an empty linked list named ANS.
  2. Start a while loop with condition L1 not equal to NULL and L2 not equal to NULL.
    1. If the value of L1 is equal to the value of L2, add the node to ANS.
    2. Else if the value of L1 is greater than the value of L2, update L2 to next of L2.
    3. Else, update L1 to next of L1.
  3. Return ANS.
Time Complexity

O(N), where N is the combined length of the two linked lists.

We are iterating through the two linked lists once, so the time complexity is O(N).

Space Complexity

O(1),

We are using constant space, so the space complexity is O(1).

Code Solution
(100% EXP penalty)
Intersection of Linked Lists
Full screen
Console