Cho hai danh sách liên kết chứa các chữ số. Ta cần nhân hai số được tạo thành từ hai danh sách liên kết này. Việc này có thể thực hiện dễ dàng bằng cách xây dựng hai số từ hai danh sách liên kết. Hãy xem một ví dụ.
Đầu vào
1 -> 2 -> NULL 2 -> 3 -> NULL
Đầu ra
2 -> 7 -> 6 -> NULL
Thuật toán
- Khởi tạo hai danh sách liên kết.
- Khởi tạo hai biến bằng 0 để lưu trữ hai số.
- Duyệt qua hai danh sách liên kết.
- Thêm từng chữ số vào biến số tương ứng ở cuối.
- Nhân hai số kết quả và lưu vào một biến.
- Tạo danh sách mới với kết quả.
- In danh sách mới.
Triển khai
Dưới đây là triển khai thuật toán trên bằng C++:
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; void addNewNode(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = *head; *head = newNode; } void multiplyTwoLinkedLists(struct Node* firstHead, struct Node* secondHead , struct Node** newLinkedListHead) { int _1 = 0, _2 = 0; while (firstHead || secondHead) { if (firstHead) { _1 = _1 * 10 + firstHead->data; firstHead = firstHead->next; } if (secondHead) { _2 = _2 * 10 + secondHead->data; secondHead = secondHead->next; } } int result = _1 * _2; while (result) { addNewNode(newLinkedListHead, result % 10); result /= 10; } } void printLinkedList(struct Node *node) { while(node != NULL) { cout << node->data << "->"; node = node->next; } cout << "NULL" << endl; } int main(void) { struct Node* firstHead = NULL; struct Node* secondHead = NULL; addNewNode(&firstHead, 1); addNewNode(&firstHead, 2); addNewNode(&firstHead, 3); printLinkedList(firstHead); addNewNode(&secondHead, 1); addNewNode(&secondHead, 2); printLinkedList(secondHead); struct Node* newLinkedListHead = NULL; multiplyTwoLinkedLists(firstHead, secondHead, &newLinkedListHead); printLinkedList(newLinkedListHead); return 0; }
Đầu ra
Nếu chạy mã trên, bạn sẽ nhận được kết quả sau:
3->2->1->NULL 2->1->NULL 6->7->4->1->NULL