Tìm bộ ba từ 3 danh sách liên kết có tổng bằng giá trị cho trước C++

Cho 3 danh sách liên kết đơn, tìm bộ ba (mỗi node từ 1 danh sách) có tổng bằng số cho trước. Ví dụ: 3 danh sách đều {1,2,3,4}, target=9 → (1,4,4).

Phương pháp: Ba vòng lặp lồng nhau

• Duyệt node a từ list1.
• Duyệt node b từ list2.
• Duyệt node c từ list3.
• Kiểm tra a->data + b->data + c->data == target.

Phức tạp O(n₁×n₂×n₃).

Ví dụ mã nguồn

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

struct Node {
    int data;
    Node* next;
};

void insert(Node** head, int data) {
    Node* n = new Node{data, *head};
    *head = n;
}

void findTriplet(Node* h1, Node* h2, Node* h3, int target) {
    bool found = false;
    for (Node* a = h1; a && !found; a = a->next)
        for (Node* b = h2; b && !found; b = b->next)
            for (Node* c = h3; c; c = c->next)
                if (a->data + b->data + c->data == target) {
                    cout << a->data << ' ' << b->data << ' ' << c->data << '\n';
                    found = true;
                    break;
                }
    if (!found) cout << "Khong tim thay triplet\n";
}

int main() {
    Node *h1=null, *h2=null, *h3=null;
    for (int x:{4,3,2,1}) insert(&h1, x);
    for (int x:{4,3,2,1}) insert(&h2, x);
    for (int x:{1,2,3,4}) insert(&h3, x);
    findTriplet(h1, h2, h3, 9);  // 1 4 4
    findTriplet(h1, h2, h3, 100); // Khong tim thay
    return 0;
}

Kết quả

1 4 4
Khong tim thay triplet