Đếm cặp từ hai danh sách liên kết có tổng 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ổng giá trị bằng k.

Ví dụ

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

Ý tưởng giải thuật

Duyệt lồng nhau qua hai danh sách (O(n×m)). Kiểm tra node1->data + node2->data == k.

Tối ưu: Có thể dùng unordered_set lưu giá trị list2, duyệt list1 kiểm tra k - node1->data có trong set không (O(n+m)).

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;
}

// Cách 1: Lồng vòng lặp O(n*m)
int countSumPairsNaive(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;
}

// Cách 2: Hiệu quả O(n+m) với unordered_set
int countSumPairsFast(ListNode* head1, ListNode* head2, int k) {
    unordered_set<int> s;
    for (ListNode* p = head2; p; p = p->next)
        s.insert(p->data);
    
    int count = 0;
    for (ListNode* p = head1; p; p = p->next)
        if (s.count(k - p->data)) 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 = 11;
    cout << "Cach 1: " << countSumPairsNaive(l1, l2, k) << endl; // 4
    cout << "Cach 2: " << countSumPairsFast(l1, l2, k) << endl;  // 4
    return 0;
}

Đầu vào

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

Đầu ra

4