C++で連結リスト表現の2つの数値を乗算する方法

ここでは、数字が格納された2つの連結リスト（リンクリスト）が与えられます。それぞれの連結リストが表す数値を乗算し、その結果を求めることが目的です。各連結リストから順に数値を構築すれば、この問題は簡単に解くことができます。具体的な例を見てみましょう。

入力例と出力例

入力：

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

出力：

2 -> 7 -> 6 -> NULL

この例では、最初のリストが「12」、2番目のリストが「23」を表しており、12 × 23 = 276 となるため、出力は「276」を表す連結リストになります。

アルゴリズム

• 2つの連結リストを初期化します。
• 2つの数値を格納するための変数を0で初期化します。
• 両方の連結リストを走査します。
  • 各桁の数字を取り出し、対応する数値変数の末尾に追加していきます（現在の値を10倍してから桁を加算）。
• 構築した2つの数値を乗算し、その結果を変数に保存します。
• 乗算結果から新しい連結リストを作成します。
• 新しい連結リストを出力します。

C++での実装

以下は、上記のアルゴリズムを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

この例では、最初のリストが「123」、2番目のリストが「21」を表しており、123 × 21 = 2583 となるため、結果のリストは「2583」を逆順に出力したものになっています。なお、addNewNode 関数は先頭にノードを挿入する仕組みのため、結果リストは桁が逆順に並びます。

注意点

この実装では、連結リストから構築した数値を int 型で保持しています。桁数が多い場合（9〜10桁以上）にはオーバーフローが発生する可能性があるため、必要に応じて long long 型を使用するか、大きな数値を扱う場合は文字列処理や多倍長整数による乗算を実装することをおすすめします。