Select Page

Count pairs from two linked lists whose sum is equal to a given value

In this problem, we have given two linked lists of size n1 and n2 with distinct elements and a value k. We need to count all pairs from both lists whose sum is equal to the value k.

Note: The pair has an element from each linked list.

Examples:

Input: list1 = 3 ->1 ->5 ->7

list2 = 8 ->2 ->5 ->3k = 10

Output: 2

The pairs are:

(5, 5) and (7, 3)

Input:list1 = 4 ->3 ->5 ->7 ->11 ->2 ->1

list2 = 2 ->3 ->4 ->5 ->6 ->8->12k = 9

Output: 5

Method 1:(Naive Approach)

In this method, we will use two loops to pick elements from both the linked lists and check whether the sum of the pair is equal to x or not.

C implementation to count pairs from both linked lists whose sum is equal to a given value

Output:

Time Complexity: The time complexity of the above method is O(n1*n2).

Space Complexity:The space complexity of the above method is O(1) which is constant.

Method 2:(By Sorting)

This method will sort the 1st linked list in ascending order and the 2nd linked list in descending order. Then, we will traverse both the linked lists from left to right to count the pairs.

Note:Here, we assume that we have sorted linked lists.

Output:

Time Complexity: The time complexity of above method is O(n1 *  logn1) +.O(n2 *  logn2).

Space Complexity:The space complexity of the above method is O(1) which is constant.