给定两个大小相同的链表（可以排序或不排序） n1 和 n2 具有不同的元素。给定一个值 十、 .问题是从两个列表中计算出其和等于给定值的所有对 十、 .
null
注： 这一对从每个链表中都有一个元素。
例如：
Input : list1 = 3->1->5->7 list2 = 8->2->5->3 x = 10Output : 2The pairs are:(5, 5) and (7, 3)Input : list1 = 4->3->5->7->11->2->1 list2 = 2->3->4->5->6->8-12 x = 9 Output : 5
方法1（天真的方法）： 使用两个循环从两个链表中拾取元素，并检查该对的和是否等于 十、 或者不是。
C++
// C++ implementation to count pairs from both linked // lists whose sum is equal to a given value #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // function to count all pairs from both the linked lists // whose sum is equal to a given value int countPairs( struct Node* head1, struct Node* head2, int x) { int count = 0; struct Node *p1, *p2; // traverse the 1st linked list for (p1 = head1; p1 != NULL; p1 = p1->next) // for each node of 1st list // traverse the 2nd list for (p2 = head2; p2 != NULL; p2 = p2->next) // if sum of pair is equal to 'x' // increment count if ((p1->data + p2->data) == x) count++; // required count of pairs return count; } // Driver program to test above int main() { struct Node* head1 = NULL; struct Node* head2 = NULL; // create linked list1 3->1->5->7 push(&head1, 7); push(&head1, 5); push(&head1, 1); push(&head1, 3); // create linked list2 8->2->5->3 push(&head2, 3); push(&head2, 5); push(&head2, 2); push(&head2, 8); int x = 10; cout << "Count = " << countPairs(head1, head2, x); return 0; } |
JAVA
// Java implementation to count pairs from both linked // lists whose sum is equal to a given value // Note : here we use java.util.LinkedList for // linked list implementation import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; class GFG { // method to count all pairs from both the linked lists // whose sum is equal to a given value static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x) { int count = 0 ; // traverse the 1st linked list Iterator<Integer> itr1 = head1.iterator(); while (itr1.hasNext()) { // for each node of 1st list // traverse the 2nd list Iterator<Integer> itr2 = head2.iterator(); Integer t = itr1.next(); while (itr2.hasNext()) { // if sum of pair is equal to 'x' // increment count if ((t + itr2.next()) == x) count++; } } // required count of pairs return count; } // Driver method public static void main(String[] args) { Integer arr1[] = { 3 , 1 , 5 , 7 }; Integer arr2[] = { 8 , 2 , 5 , 3 }; // create linked list1 3->1->5->7 LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1)); // create linked list2 8->2->5->3 LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2)); int x = 10 ; System.out.println( "Count = " + countPairs(head1, head2, x)); } } |
Python3
# Python3 implementation to count pairs from both linked # lists whose sum is equal to a given value # A Linked list node class Node: def __init__( self ,data): self .data = data self . next = None # function to insert a node at the # beginning of the linked list def push(head_ref,new_data): new_node = Node(new_data) #new_node.data = new_data new_node. next = head_ref head_ref = new_node return head_ref # function to count all pairs from both the linked lists # whose sum is equal to a given value def countPairs(head1, head2, x): count = 0 #struct Node p1, p2 # traverse the 1st linked list p1 = head1 while (p1 ! = None ): # for each node of 1st list # traverse the 2nd list p2 = head2 while (p2 ! = None ): # if sum of pair is equal to 'x' # increment count if ((p1.data + p2.data) = = x): count + = 1 p2 = p2. next p1 = p1. next # required count of pairs return count # Driver program to test above if __name__ = = '__main__' : head1 = None head2 = None # create linked list1 3.1.5.7 head1 = push(head1, 7 ) head1 = push(head1, 5 ) head1 = push(head1, 1 ) head1 = push(head1, 3 ) # create linked list2 8.2.5.3 head2 = push(head2, 3 ) head2 = push(head2, 5 ) head2 = push(head2, 2 ) head2 = push(head2, 8 ) x = 10 print ( "Count = " ,countPairs(head1, head2, x)) # This code is contributed by AbhiThakur |
C#
// C# implementation to count pairs from both linked // lists whose sum is equal to a given value using System; using System.Collections.Generic; // Note : here we use using System.Collections.Generic for // linked list implementation class GFG { // method to count all pairs from both the linked lists // whose sum is equal to a given value static int countPairs(List< int > head1, List< int > head2, int x) { int count = 0; // traverse the 1st linked list foreach ( int itr1 in head1) { // for each node of 1st list // traverse the 2nd list int t = itr1; foreach ( int itr2 in head2) { // if sum of pair is equal to 'x' // increment count if ((t + itr2) == x) count++; } } // required count of pairs return count; } // Driver code public static void Main(String []args) { int []arr1 = {3, 1, 5, 7}; int []arr2 = {8, 2, 5, 3}; // create linked list1 3->1->5->7 List< int > head1 = new List< int >(arr1); // create linked list2 8->2->5->3 List< int > head2 = new List< int >(arr2); int x = 10; Console.WriteLine( "Count = " + countPairs(head1, head2, x)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript implementation to count pairs from both linked // lists whose sum is equal to a given value // Note : here we use java.util.LinkedList for // linked list implementation // method to count all pairs from both the linked lists // whose sum is equal to a given value function countPairs( head1, head2 , x) { var count = 0; // traverse the 1st linked list for ( var itr1 of head1) { // for each node of 1st list // traverse the 2nd list for ( var itr2 of head2) { // if sum of pair is equal to 'x' // increment count if ((itr1 + itr2) == x) count++; } } // required count of pairs return count; } // Driver method var arr1 = [ 3, 1, 5, 7 ]; var arr2 = [ 8, 2, 5, 3 ]; // create linked list1 3->1->5->7 var head1 = (arr1); // create linked list2 8->2->5->3 var head2 = arr2; var x = 10; document.write( "Count = " + countPairs(head1, head2, x)); // This code is contributed by Rajput-Ji </script> |
输出：
Count = 2
时间复杂性： O（n1*n2） 辅助空间： O（1） 方法2（排序）： 按升序对第一个链接列表和第二个链接列表进行排序 使用合并排序按降序列出 技巧现在，按照以下方式从左到右遍历这两个列表：
算法：
countPairs(list1, list2, x) Initialize count = 0 while list != NULL and list2 != NULL if (list1->data + list2->data) == x list1 = list1->next list2 = list2->next count++ else if (list1->data + list2->data) > x list2 = list2->next else list1 = list1->next return count
为简单起见，下面给出的实现假设list1按升序排序，list2按降序排序。
C++
// C++ implementation to count pairs from both linked // lists whose sum is equal to a given value #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // function to count all pairs from both the linked // lists whose sum is equal to a given value int countPairs( struct Node* head1, struct Node* head2, int x) { int count = 0; // sort head1 in ascending order and // head2 in descending order // sort (head1), sort (head2) // For simplicity both lists are considered to be // sorted in the respective orders // traverse both the lists from left to right while (head1 != NULL && head2 != NULL) { // if this sum is equal to 'x', then move both // the lists to next nodes and increment 'count' if ((head1->data + head2->data) == x) { head1 = head1->next; head2 = head2->next; count++; } // if this sum is greater than x, then // move head2 to next node else if ((head1->data + head2->data) > x) head2 = head2->next; // else move head1 to next node else head1 = head1->next; } // required count of pairs return count; } // Driver program to test above int main() { struct Node* head1 = NULL; struct Node* head2 = NULL; // create linked list1 1->3->5->7 // assumed to be in ascending order push(&head1, 7); push(&head1, 5); push(&head1, 3); push(&head1, 1); // create linked list2 8->5->3->2 // assumed to be in descending order push(&head2, 2); push(&head2, 3); push(&head2, 5); push(&head2, 8); int x = 10; cout << "Count = " << countPairs(head1, head2, x); return 0; } |
JAVA
// Java implementation to count pairs from both linked // lists whose sum is equal to a given value // Note : here we use java.util.LinkedList for // linked list implementation import java.util.Arrays; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; class GFG { // method to count all pairs from both the linked lists // whose sum is equal to a given value static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x) { int count = 0 ; // sort head1 in ascending order and // head2 in descending order Collections.sort(head1); Collections.sort(head2,Collections.reverseOrder()); // traverse both the lists from left to right Iterator<Integer> itr1 = head1.iterator(); Iterator<Integer> itr2 = head2.iterator(); Integer num1 = itr1.hasNext() ? itr1.next() : null ; Integer num2 = itr2.hasNext() ? itr2.next() : null ; while (num1 != null && num2 != null ) { // if this sum is equal to 'x', then move both // the lists to next nodes and increment 'count' if ((num1 + num2) == x) { num1 = itr1.hasNext() ? itr1.next() : null ; num2 = itr2.hasNext() ? itr2.next() : null ; count++; } // if this sum is greater than x, then // move itr2 to next node else if ((num1 + num2) > x) num2 = itr2.hasNext() ? itr2.next() : null ; // else move itr1 to next node else num1 = itr1.hasNext() ? itr1.next() : null ; } // required count of pairs return count; } // Driver method public static void main(String[] args) { Integer arr1[] = { 3 , 1 , 5 , 7 }; Integer arr2[] = { 8 , 2 , 5 , 3 }; // create linked list1 3->1->5->7 LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1)); // create linked list2 8->2->5->3 LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2)); int x = 10 ; System.out.println( "Count = " + countPairs(head1, head2, x)); } } |
输出：
Count = 2
时间复杂性： O（n1*logn1）+O（n2*logn2） 辅助空间： O（1） 排序将更改节点的顺序。如果顺序很重要，则可以创建并使用链接列表的副本。
方法3（散列）： 哈希表是使用 C++中的无序序集 .我们将所有第一个链表元素存储在哈希表中。对于第二个链表的元素，我们从 十、 并在哈希表中检查结果。如果结果存在，我们增加 计数 .
C++
// C++ implementation to count pairs from both linked // lists whose sum is equal to a given value #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // function to count all pairs from both the linked // lists whose sum is equal to a given value int countPairs( struct Node* head1, struct Node* head2, int x) { int count = 0; unordered_set< int > us; // insert all the elements of 1st list // in the hash table(unordered_set 'us') while (head1 != NULL) { us.insert(head1->data); // move to next node head1 = head1->next; } // for each element of 2nd list while (head2 != NULL) { // find (x - head2->data) in 'us' if (us.find(x - head2->data) != us.end()) count++; // move to next node head2 = head2->next; } // required count of pairs return count; } // Driver program to test above int main() { struct Node* head1 = NULL; struct Node* head2 = NULL; // create linked list1 3->1->5->7 push(&head1, 7); push(&head1, 5); push(&head1, 1); push(&head1, 3); // create linked list2 8->2->5->3 push(&head2, 3); push(&head2, 5); push(&head2, 2); push(&head2, 8); int x = 10; cout << "Count = " << countPairs(head1, head2, x); return 0; } |
JAVA
// Java implementation to count pairs from both linked // lists whose sum is equal to a given value // Note : here we use java.util.LinkedList for // linked list implementation import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; class GFG { // method to count all pairs from both the linked lists // whose sum is equal to a given value static int countPairs(LinkedList<Integer> head1, LinkedList<Integer> head2, int x) { int count = 0 ; HashSet<Integer> us = new HashSet<Integer>(); // insert all the elements of 1st list // in the hash table(unordered_set 'us') Iterator<Integer> itr1 = head1.iterator(); while (itr1.hasNext()) { us.add(itr1.next()); } Iterator<Integer> itr2 = head2.iterator(); // for each element of 2nd list while (itr2.hasNext()) { // find (x - head2->data) in 'us' if (!(us.add(x - itr2.next()))) count++; } // required count of pairs return count; } // Driver method public static void main(String[] args) { Integer arr1[] = { 3 , 1 , 5 , 7 }; Integer arr2[] = { 8 , 2 , 5 , 3 }; // create linked list1 3->1->5->7 LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1)); // create linked list2 8->2->5->3 LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2)); int x = 10 ; System.out.println( "Count = " + countPairs(head1, head2, x)); } } |
Python3
# Python3 implementation to count pairs from both linked # lists whose sum is equal to a given value ''' A Linked list node ''' class Node: def __init__( self ): self .data = 0 self . next = None # function to add a node at the # beginning of the linked list def push(head_ref, new_data): ''' allocate node ''' new_node = Node() ''' put in the data ''' new_node.data = new_data; ''' link the old list to the new node ''' new_node. next = (head_ref); ''' move the head to point to the new node ''' (head_ref) = new_node; return head_ref # function to count all pairs from both the linked # lists whose sum is equal to a given value def countPairs(head1, head2, x): count = 0 ; us = set () # add all the elements of 1st list # in the hash table(unordered_set 'us') while (head1 ! = None ): us.add(head1.data); # move to next node head1 = head1. next ; # for each element of 2nd list while (head2 ! = None ): # find (x - head2.data) in 'us' if ((x - head2.data) in us): count + = 1 # move to next node head2 = head2. next ; # required count of pairs return count; # Driver program to test above if __name__ = = '__main__' : head1 = None ; head2 = None ; # create linked list1 3.1.5.7 head1 = push(head1, 7 ); head1 = push(head1, 5 ); head1 = push(head1, 1 ); head1 = push(head1, 3 ); # create linked list2 8.2.5.3 head2 = push(head2, 3 ); head2 = push(head2, 5 ); head2 = push(head2, 2 ); head2 = push(head2, 8 ); x = 10 ; print ( "Count =" , countPairs(head1, head2, x)); # This code is contributed by rutvik_56 |
C#
// C# implementation to count pairs from both linked // lists whose sum is equal to a given value // Note : here we use java.util.LinkedList for // linked list implementation using System; using System.Collections.Generic; class GFG { // method to count all pairs from both the linked lists // whose sum is equal to a given value static int countPairs(List< int > head1, List< int > head2, int x) { int count = 0; HashSet< int > us = new HashSet< int >(); // insert all the elements of 1st list // in the hash table(unordered_set 'us') foreach ( int itr1 in head1) { us.Add(itr1); } // for each element of 2nd list foreach ( int itr2 in head2) { // find (x - head2->data) in 'us' if (!(us.Contains(x - itr2))) count++; } // required count of pairs return count; } // Driver code public static void Main(String[] args) { int []arr1 = {3, 1, 5, 7}; int []arr2 = {8, 2, 5, 3}; // create linked list1 3->1->5->7 List< int > head1 = new List< int >(arr1); // create linked list2 8->2->5->3 List< int > head2 = new List< int >(arr2); int x = 10; Console.WriteLine( "Count = " + countPairs(head1, head2, x)); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript implementation to count pairs // from both linked lists whose sum is equal // to a given value // A Linked list node class Node { constructor(new_data) { this .data = new_data; this .next = null ; } }; // Function to count all pairs from both the linked // lists whose sum is equal to a given value function countPairs(head1, head2, x) { let count = 0; let us = new Set(); // Insert all the elements of 1st list // in the hash table(unordered_set 'us') while (head1 != null ) { us.add(head1.data); // Move to next node head1 = head1.next; } // For each element of 2nd list while (head2 != null ) { // Find (x - head2.data) in 'us' if (us.has(x - head2.data)) count++; // Move to next node head2 = head2.next; } // Required count of pairs return count; } // Driver code let head1 = null ; let head2 = null ; // Create linked list1 3.1.5.7 head1 = new Node(3) head1.next = new Node(1) head1.next.next = new Node(5) head1.next.next.next = new Node(7) // Create linked list2 8.2.5.3 head2 = new Node(8) head2.next = new Node(2) head2.next.next = new Node(5) head2.next.next.next = new Node(3) let x = 10; document.write( "Count = " + countPairs(head1, head2, x)); // This code is contributed by Potta Lokesh </script> |
输出：
Count = 2
时间复杂性： O（n1+n2） 辅助空间： O（n1），对于较小的数组应该创建哈希表，以降低空间复杂度。 本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
