### Problem Statement

We will be given two linked lists and an integer target as input, and we need to count pairs of integers in both lists such that each element of the pair belongs to different lists and their sum is equal to the given target integer.

### Problem Statement Understanding

To understand the problem statement, letâ€™s take an example.

If the linked lists given to us are 1â†’3â†’5â†’8â†’NULL, 6â†’4â†’1â†’NULL, and the target = 9. Then, according to the problem statement:

- We need to find pairs of integers such that each element of the pair belongs to a different list, and their sum is equal to 9.
- All such pairs are - (3,6), (8,1) and (5,4)
- There are three possible pairs, so; we need to print 3 as output, i.e., the total count of possible pairs.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letâ€™s move to the approach section.

### Approach 1

The naive approach that comes to our mind is that first, select a node in the first list and for each selected node in the first list, iterate in the second list and check if the sum of nodeâ€™s (selected node from first list + node from the second list) is equal to the target or not.

**Time Complexity:** O(N^{2}), N is the number of nodes in a list.

**Space Complexity:** O(1)

The above approach gives the correct result, but its time complexity is high. Can we reduce the time complexity? Let us find out If we can do so in the below approach.

### Approach 2

- In this approach, we store all elements of the first list in a HashSet.
- Then, we iterate on the elements of the second list and find if the difference in the value of the current element of the second list and target exists in hash or not.
- If it exists in the HashSet, then we will increase the count by one.

### Algorithm

1) Initialize a **result** variable with 0 and create an unordered set.

2) Push all elements of the first list in the set created above.

3) Run a while loop till **head2** (pointer to the second list) is not NULL.

- Check if
**(target - head2->data)**exists in the set or not- If it exists then, increment the
**result**by one.

- If it exists then, increment the
- Move the pointer
**head2**forward by one node.

4) After the loop is executed, return**result**from the function.

### Code Implementation

#includeusing namespace std; class Node{ public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; int countPairs(Node* head1, Node* head2,int target) { int result = 0; unordered_set hash_set; //insert all elements of first list in //the hash set while (head1 != NULL) { hash_set.insert(head1->data); head1 = head1->next; } // iterate on each elements of second list while (head2 != NULL) { //find if (target - currentData) exists //in the hashset if (hash_set.find(target - head2->data) != hash_set.end()) result++; head2 = head2->next; } // return the result return result; } int main(void){ Node* first = NULL; first = new Node(1); first->next = new Node(3); first->next->next = new Node(5); first->next->next->next = new Node(8); Node* second = NULL; second = new Node(6); second->next = new Node(4); second->next->next = new Node(1); cout<<"Count of pairs having sum "<<9<<" are: "; cout<

#### Output

Count of pairs having sum 9 are: 3

**Time Complexity:** O(n), n is the number of nodes in a list.

**Space Complexity:** O(n), n is the number of nodes in a list.

In the above approach, we are using extra space to store the elements in a hash set. Can we reduce the extra space used? Let us find out If we can do so in the below approach.

### Approach 3

- At first, we need to
**sort the first list in ascending order and the second list in descending order**. - The above step is performed so that we can predict whether moving forward in the lists is going to increase our current sum or decrease it.
- It is evident that moving forward in the first list is going to increase the pair sum, and moving forward in the second one is going to decrease it.
- Now, we will initialize two different pointers at the head of both lists.
- We will compute the sum pointed by the pointers in each step, and If the
**sum is equal to the target**, we will increase our result by one and move both pointers simultaneously. - If the
**sum is less than the target**, we need to increase it so we will move the pointer of the first list forward by one node. - Else, we will move the pointer of the second list by one node.

### Algorithm

1) Sort the **first list in ascending order and the second list in descending order**.

2) Initialize a variable **result** by 0.

3) Run a while loop till any one of **first** or **second** becomes NULL.

4) Calculate **sum** as the sum of data of nodes pointed by **first** and **second** pointers.

5) If the **sum** is equal to the **target**, increase the **result** by one and move both pointers forward by one node.

6) If the **sum** is greater than the **target**, move the **second** pointer forward by one node.

7) Else, move the **first** pointer forward by one node.

**Note:** For simplicity, in dry run and code implementation, we took the first and the second linked lists, which are already sorted in ascending and descending order, respectively. If you want to know how to sort a linked list, please feel free to refer to this article for sorting related concepts of linked list. Also, inside the code implementation, we haven't provided the sorting function (function to sort the linked list); if you want to take unsorted linked lists, please sort them in proper format (the first list will be sorted in ascending order and the second list in descending order) using code from the above-mentioned article, before passing them to **countPairs()** function in the code.

Also, note that to sort a linked list in descending order, you can first sort the linked list in ascending order, and then you can reverse the sorted linked list.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node{ public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; int countPairs(Node* first, Node* second,int target) { int result = 0; // iterate both lists while (first != NULL && second != NULL) { //calculate 'sum' int sum = first->data + second->data; //if sum equals target, increase result by 1 //and move both pointers if (sum == target) { first = first->next; second = second->next; result++; } // if sum is more than target, move // second pointer else if (sum > target) second = second->next; // else move first pointer else first = first->next; } // required count of pairs return result; } int main(void){ Node* first = NULL; first = new Node(1); first->next = new Node(3); first->next->next = new Node(5); first->next->next->next = new Node(8); Node* second = NULL; second = new Node(6); second->next = new Node(4); second->next->next = new Node(1); cout<<"Count of pairs having sum "<<9<<" are: "; cout<

#### Output

Count of pairs having sum 9 are: 3

**Time Complexity:** O(N log N), N is the number of nodes in the list

**Space Complexity:** O(1)

So, in this blog, we have tried to explain how to count pairs from two linked lists whose sum is equal to a given value, most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.