Nhân hai số biểu diễn bằng danh sách liên kết C++

Cho hai danh sách liên kết đơn, mỗi nút chứa một chữ số. Tạo số từ danh sách, nhân hai số, lưu kết quả vào danh sách mới.

Ví dụ

List1: 1 → 2 → 3 (số 123)
List2: 1 → 2 (số 12)
Kết quả: 123 × 12 = 1476 → List: 1 → 4 → 7 → 6

Thuật toán

• Duyệt list1, list2 để xây dựng số nguyên num1, num2.
• Nhân: result = num1 * num2.
• Tách các chữ số của result tạo list mới (thêm đầu để giữ thứ tự).

Triển khai C++

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

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

void push(Node** head, int data) {
    Node* newNode = new Node{data, *head};
    *head = newNode;
}

void multiplyLists(Node* l1, Node* l2, Node** res) {
    long long n1 = 0, n2 = 0;
    while (l1) { n1 = n1 * 10 + l1->data; l1 = l1->next; }
    while (l2) { n2 = n2 * 10 + l2->data; l2 = l2->next; }

    long long prod = n1 * n2;
    if (prod == 0) { push(res, 0); return; }
    while (prod) { push(res, prod % 10); prod /= 10; }
}

void printList(Node* head) {
    while (head) { cout << head->data << "->"; head = head->next; }
    cout << "NULL" << endl;
}

int main() {
    Node *l1 = nullptr, *l2 = nullptr, *res = nullptr;
    push(&l1, 3); push(&l1, 2); push(&l1, 1); // 123
    push(&l2, 2); push(&l2, 1);               // 12
    multiplyLists(l1, l2, &res);
    printList(res); // 1->4->7->6->NULL
    return 0;
}

Kết quả

1->4->7->6->NULL

Lưu ý: Cách này bị giới hạn bởi kiểu dữ liệu (long long). Với số rất lớn cần nhân trực tiếp trên danh sách/chuỗi.