คูณสองตัวเลขที่แทนด้วยลิงก์ลิสต์เป็นลิสต์ที่สามใน C++

โจทย์

ได้รับลิงก์ลิสต์สองตัวที่มีหลักตัวเลข เราต้องคูณสองตัวเลขที่สร้างจากลิงก์ลิสต์ สามารถทำได้ง่ายๆ โดยการสร้างตัวเลขจากลิงก์ลิสต์ทั้งสอง มาดูตัวอย่างกัน

อินพุต

1 -> 2 -> NULL
2 -> 3 -> NULL

เอาต์พุต

2 -> 7 -> 6 -> NULL

อัลกอริธึม

• กำหนดลิงก์ลิสต์สองตัว
• กำหนดตัวแปรสองตัวด้วย 0 เพื่อเก็บตัวเลขสองตัว
• วนลูปผ่านลิงก์ลิสต์ทั้งสอง
  • เพิ่มแต่ละหลักเข้าไปในตัวแปรตัวเลขที่เกี่ยวข้องท้ายสุด
• คูณตัวเลขที่ได้และเก็บผลลัพธ์ในตัวแปร
• สร้างลิสต์ใหม่ด้วยผลลัพธ์
• พิมพ์ลิสต์ใหม่

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน 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; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

3->2->1->NULL
2->1->NULL
6->7->4->1->NULL