![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012316328-Article_207.png\")
<\/p>\n<\/p>\n
This blog will discuss an important problem of count pairs from two linked with given sum Such problems do come in interviews.
\nBefore solving the problem, it\u2019s recommended that a known basic traversal in the Linked List check Linked List.
\nIn 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.
\nLet\u2019s look at the problem statement of count pairs from two linked with given sum for a better understanding.<\/p>\n
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.<\/p>\n
To understand the problem statement, let\u2019s take an example.<\/p>\n
If the linked lists given to us are 1\u21923\u21925\u21928\u2192NULL, 6\u21924\u21921\u2192NULL, and the target = 9. Then, according to the problem statement:<\/p>\n
At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.<\/p>\n
Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n
Let\u2019s move to the approach section.<\/p>\n
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\u2019s (selected node from first list + node from the second list) is equal to the target or not.<\/p>\n
Time Complexity of count pairs from two linked with given sum:<\/strong> O(N2<\/sup>), N is the number of nodes in a list. 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.<\/p>\n Run a while loop till head2<\/strong> (pointer to the second list) is not NULL.<\/p>\n Check if (target – head2->data)<\/strong> exists in the set or not<\/p>\n Move the pointer head2<\/strong> forward by one node.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n
\nSpace Complexity of count pairs from two linked with given sum:<\/strong> O(1)<\/p>\nApproach 2 of count pairs from two linked with given sum<\/h2>\n
\n
Algorithm of count pairs from two linked with given sum<\/h2>\n
\n
\n
\n
Code Implementation of count pairs from two linked with given sum<\/h2>\n\t\t\t\t\t\t