দুই লিংকড লিস্ট থেকে যোগফল নির্দিষ্ট জোড়া গণনা C++-এ

দুই লিংকড লিস্ট দেওয়া থাকলে, একটা লিস্টের একটি নোড এবং অন্য লিস্টের একটি নোড দিয়ে জোড়া বানাতে হবে যাতে তাদের যোগফল একটি নির্দিষ্ট মান k-এর সমান হয়। মোট কতটি এমন জোড়া আছে তা বের করতে হবে।

উদাহরণ

লিস্ট ১: 5 → 7 → 8 → 10 → 11

লিস্ট ২: 6 → 4 → 3 → 2 → 0

k = 11

বৈধ জোড়া: (5,6), (7,4), (8,3) → মোট 3টি (নোট: আউটপুটে ৪ বলা হয়েছে কিন্তু সঠিক ৩টি)

অ্যালগরিদম

1. দুই নেস্টেড লুপ চালান: প্রথম লিস্টের প্রতিটি নোডের জন্য দ্বিতীয় লিস্টের সব নোড চেক করুন।
2. যদি first->data + second->data == k হয়, তবে কাউন্ট বাড়ান।
3. সময় জটিলতা: O(n×m)

C++ কোড উদাহরণ

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

class ListNode {
public:
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(NULL) {}
};

ListNode* createList(vector& v) {
    if (v.empty()) return NULL;
    ListNode* head = new ListNode(v[0]);
    ListNode* curr = head;
    for (int i = 1; i < v.size(); i++) {
        curr->next = new ListNode(v[i]);
        curr = curr->next;
    }
    return head;
}

int countSumPairs(ListNode* head1, ListNode* head2, int k) {
    int count = 0;
    for (ListNode* p1 = head1; p1; p1 = p1->next) {
        for (ListNode* p2 = head2; p2; p2 = p2->next) {
            if (p1->data + p2->data == k) count++;
        }
    }
    return count;
}

int main() {
    vector v1 = {5, 7, 8, 10, 11};
    vector v2 = {6, 4, 3, 2, 0};
    int k = 11;
    
    ListNode* l1 = createList(v1);
    ListNode* l2 = createList(v2);
    
    cout << "Count: " << countSumPairs(l1, l2, k);
    return 0;
}

ইনপুট

v1={5,7,8,10,11}, v2={6,4,3,2,0}, k=11

আউটপুট

3