Đưa ra hai danh sách được liên kết với các chữ số trong đó. Chúng ta cần nhân hai số được tạo thành bởi danh sách liên kết. Nó có thể được thực hiện dễ dàng bằng cách tạo thành các số từ hai danh sách được 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 được liên kết.
- Khởi tạo hai biến bằng 0 để lưu trữ hai số.
- Lặp lại hai danh sách được liên kết.
- Thêm từng chữ số vào biến số tương ứng ở cuối.
- Nhân các số có kết quả và lưu trữ kết quả trong một biến.
- Tạo một danh sách mới với kết quả.
- In danh sách mới.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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 bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
3->2->1->NULL 2->1->NULL 6->7->4->1->NULL