Intersection of Linked Lists

Posted: 12 Dec, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem