【C++】連結リストで表された2つの数値を乗算して新しいリストに結果を格納する方法

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

入力と出力の例

入力

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

出力

2 -> 7 -> 6 -> NULL

この例では、1つ目の連結リストが表す数値は「12」、2つ目の連結リストが表す数値は「23」です。12 × 23 = 276 となるため、出力は「276」を表す連結リストになります。

アルゴリズム

• 2つの連結リストを初期化します。
• 2つの数値を格納するための変数を0で初期化します。
• 2つの連結リストをそれぞれ走査します。
  • 各桁の数字を、「現在の値 × 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;
}

実装のポイント

この実装で重要なのは、連結リストを走査しながら「_1 = _1 * 10 + firstHead->data」という式で数値を構築している点です。これにより、リストの先頭から順に各桁を処理しつつ、正しい数値を組み立てることができます。

また、乗算結果を連結リストへ戻す際は、result % 10 で取り出した下一桁を順番に新しいノードとして先頭に追加しています。addNewNode 関数は常にリストの先頭にノードを挿入するため、下一桁から順に追加しても、最終的に正しい桁順の連結リストが完成します。

注意点：オーバーフローに気をつける

このアプローチでは、連結リストから構築した数値を int 型の変数に格納しています。そのため、リストの桁数が大きくなるとオーバーフローが発生する可能性があります。非常に長い連結リストを扱う場合は、long long 型を使用するか、あるいは桁ごとの乗算と繰り上がり処理を行う方式に変更する必要があります。

出力

上記のコードを実行すると、次のような結果が得られます。

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

ノードが先頭に挿入される仕様上、表示は逆順になりますが、最初のリストが表す数値は「321」、2つ目のリストが表す数値は「21」です。321 × 21 = 6741 となるため、3つ目のリストに「6741」が正しく格納されていることが確認できます。