हमें दो लिंक्ड लिस्ट दी गई हैं और कार्य है उनके पूर्णांक तत्वों का उपयोग करके जोड़े बनाना जिनका योग दिए गए मान k के बराबर हो।
इनपुट - v1 = {5,7,8,10,11}, v2 = {6,4,3,2,0}, k = 11
आउटपुट - दो लिंक्ड लिस्ट से योग k वाले जोड़ों की संख्या: 4
उपयोग किया गया दृष्टिकोण
- दो वेक्टर्स से लिंक्ड लिस्ट बनाएं।
- पहली लिस्ट के प्रत्येक नोड के लिए, दूसरी लिस्ट के सभी नोड्स को पार करें।
- यदि
first->data + second->data == kतो काउंट बढ़ाएं। - समय जटिलता: O(n×m)
- अनुकूलन: दूसरी लिस्ट के तत्वों को अनऑर्डर्ड सेट में स्टोर करके O(n+m) में किया जा सकता है।
उदाहरण (C++ कोड)
#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode *next;
ListNode(int data) {
this->data = data;
next = NULL;
}
};
ListNode* CreateList(vector<int> v) {
ListNode* start = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++) {
ListNode* ptr = start;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = new ListNode(v[i]);
}
return start;
}
int sum_pair(ListNode* start1, ListNode* start2, int k) {
int count = 0;
for (ListNode* first = start1; first != NULL; first = first->next) {
for (ListNode* second = start2; second != NULL; second = second->next) {
if (first->data + second->data == k)
count++;
}
}
return count;
}
int main() {
vector<int> v1 = {5,7,8,10,11};
ListNode* start1 = CreateList(v1);
vector<int> v2 = {6,4,3,2,0};
ListNode* start2 = CreateList(v2);
int k = 11;
cout << "Count of pairs from two linked lists whose sum is equal to a given value k are: " << sum_pair(start1, start2, k);
return 0;
} आउटपुट
Count of pairs from two linked lists whose sum is equal to a given value k are: 4
