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

## Introduction

This blog will discuss an important problem of counting pairs from two linked lists whose sum is equal to a given value. Such problems do come in interviews.

Before solving the problem, it’s recommended that a known basic traversal in the Linked List check Linked List.

In this blog, we dive deep into each detail to get a number of pairs from two linked lists whose sum is equal to a given value.

Let’s look at the problem statement for this problem.

## Problem Statement

We will be given a head pointer of two linked lists of size n and m of distinct elements and an integer target as input, and the problem is to count all pairs from both lists whose sum is equal to the given value target, i.e., Count pairs from two linked lists whose sum is equal to a given value target.

Example 1

``````Input-
List1 = 1->2->3->5->NULL
List2 = 2->4->5->10->12->NULL
Target= 7``````
``Output: 3``

Explanation:

Pairs : {(2,5) ,(3,4) ,(5,2)} These are 3 pairs whose sum is equal to target = 7.

Example 2

``````Input-
List1 = 1->3->5->8->NULL
List2 = 6->4->1->NULL
Target= 9``````
``Output: 3``

Explanation:

Pairs : {(3,6) ,(8,1) ,(5,4)} These are 3 pairs whose sum is equal to target = 9.

## Approach 1

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to select a node in the first linked list for each selected element. We iterate over every node in the second linked list and count the pair whose sum is equal to the target value.

Now let’s look at the PseudoCode.

### PseudoCode

Algorithm

``````//Counts pairs from two linked lists whose sum is equal to a given //value
// pass list1,list2 and value target
countPairs(list1, list2, target)
Intialize count = 0
while list1 != NULL
Data1 = list1_value
while list2 != NULL
Data2 = list2_value
if Data1 + Data2 is equal to target
Increase count by 1
list2 = list2_next
list1 = list1_next

Return count``````

### CODE IN C++

``````#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int value;    //stores data of linked list
Node *next;   //pointer for next node
Node(int data){  //constructor to construct new node
value=data;  // with given data
next=NULL;
}
};

/* function to count pairs from two linked lists whose sum is equal to given value */
int ans=0; //stores the count of pairs with given sum
while(temp != NULL){   // traverse the second linked list
int data2 = temp->value;
if(data1 + data2 == target) //check if pair has equal sum or not
ans++;
temp=temp->next;
}
}
return ans;
}
int main(){

//store target
int target = 7;
cout<<ans<<endl;
}``````
``````Input:
target = 7
Output: 3``````

Time Complexity: O(n*m) where n = size of first linked list and m=size of second linked list.

This is because we iterate through two nested loops. Hence it’s O(n*m).

Space Complexity: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n*m) time which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

## Approach 2

One of the good approaches to count pairs from two linked lists whose sum is equal to a given value is by using a hash table

Now we can formulate our approach:

1. We store all elements of the first linked list in a HashSet.
2. Now iterate over the second linked list.
3. For each element, we have to check if (target - element) exists in the hash set or not and increase the answer accordingly.

Let’s look at the Code.

### CODE IN C++

``````#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int value;    //stores data of linked list
Node *next;   //pointer for next node
Node(int data){  //constructor to construct new node
value=data;  // with given data
next=NULL;
}
};

//declaring hashset for storing elements of first linked list
unordered_set<int> hash_set;
int ans =0;
while(head1!=NULL){ // iterate over first list
hash_set.insert(head1->value); //store the element in list in hash
}
if(hash_set.find(target-data)!=hash_set.end())
ans++;
}

return ans;

}

int main(){

//store target
int target = 7;
cout<<ans<<endl;
}``````
``````Input:
target = 7
Output: 3``````

Time Complexity: O(n + m) where n = size of first linked list and m=size of second linked list.

Since we traverse both lists once and access the hash table in O(1) time, the overall complexity is O(n + m).

Space complexity: O(n) as a form of storing the first list in a hash table.

## Approach 3

There is another efficient approach with two pointers without any extra space. But It works on sorted linked lists. So first, we efficiently sort the list by using merge-sort in the list.

Note: You can practice Sort the LinkedList problem for better clarity regarding the sorting on the list.

Now we can formulate our approach:

1. We first sort first linked list in increasing order and the second linked list in descending order.
2. Take two pointers saying pointer1 and pointer2. Initially, pointer1 points to the starting node of the first linked list, and pointer2 points to the starting node of the second linked list.
3. Now iterate on both lists in the following ways:
1. If the pointer1-value + pointer2-value is greater than the target, it means we have to decrease the sum, so we have to move pointer2 by one node.
2. If pointer1-value + pointer2-value is less than the target, it means we have to increase sum, so we have to move pointer1 by one node.
3. If pointer1-value + pointer2-value is equal to target. Increase our count and move both pointer1 and pointer2 by one node.
4. Return our count if any pointer reaches its NULL.

Let’s look at the Code.

### CODE IN C++

``````#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int value;    //stores data of linked list
Node *next;   //pointer for next node
Node(int data){  //constructor to construct new node
value=data;  // with given data
next=NULL;
}
};

/* function to count pairs from two linked lists whose sum is equal to a given value */
//intialise both pointer with thier starting node.
int ans = 0;
while(pointer1 != NULL && pointer2 != NULL){
int data1 = pointer1 -> value;
int data2 = pointer2 -> value;
if(data1 + data2 > target)
pointer2 = pointer2 -> next;

else if(data1 + data2 < target)
pointer1 = pointer1 -> next;

else {
ans++;
pointer2 = pointer2 -> next;
pointer1 = pointer1 -> next;
}
}
return ans;
}

int main(){

//store target
int target = 7;
cout<<ans<<endl;
}``````
``````Input:
target = 7
Output: 3``````

Time Complexity: O(nlogn + mlogm) where n = size of first linked list and m=size of second linked list.

We sort both list in O(nlogn + mlogm) +traverse the both list in worst case O(n + m), so overall complexity is O(nlogn + mlogm).

Space complexity: O(1) at the worst case because no extra space is used.

1. Insertion and deletion operations can be implemented very easily, and these are not costly as they do not require the shifting of elements.
2. They are dynamic. Hence, we can change their size whenever required.
3. Stacks and queues can be implemented very easily using Linked Lists.

### How does merge sort for linked list work?

The merge sort algorithm is a divide and conquers algorithm it divides the list into smaller sublists until each sublist contains only a single element, and a list of size one is always sorted; using this property, it merges two sorted sublists into a single sorted list.

### Can we use two pointer approach without sorting the lists?

No, Because in the unsorted list we can’t decide whether its next element is greater or less than the current element. So we don’t move our pointer to increase or decrease the sum.

## Conclusion

This article taught us how to solve the problem of data structure, i.e., count pairs from two linked lists whose sum is equal to a given value. We also saw how to approach the problem using a naive approach followed by two efficient solutions. We discussed an iterative implementation and some basic traversal in linked lists using examples, pseudocode, and code in detail.

We hope you understand how we can apply two pointer approach or use of hash set in such problems.

Now, we recommend you to solve some problems based on the concepts of this problem—another similar problem is the Number of pairs with a given sum

More suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the CodeStudio. Enroll in our courses, refer to the test series and problems available and look at the interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!! 