Đếm cặp từ hai danh sách liên kết có tích bằng k trong C++

Giới thiệu

Cho hai danh sách liên kết đơn và số k. Đếm số cặp (node1 từ list1, node2 từ list2) có tích giá trị bằng k.

Ví dụ

List1: 5→7→8→10→11, List2: 6→4→3→2→0, k = 20 → Cặp: (5,4), (10,2) → Kết quả: 2

Ý tưởng giải thuật

Duyệt lồng nhau qua hai danh sách (O(n×m)). Với mỗi node1, duyệt tất cả node2, kiểm tra node1->data * node2->data == k.

Ví dụ triển khai (C++)

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

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

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

int countProductPairs(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<int> v1 = {5, 7, 8, 10, 11};
    vector<int> v2 = {6, 4, 3, 2, 0};
    ListNode* l1 = createList(v1);
    ListNode* l2 = createList(v2);
    int k = 20;
    cout << "So cap co tich = " << k << ": " << countProductPairs(l1, l2, k); // 2
    return 0;
}

Đầu vào

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

Đầu ra

2