C++のリンクリストで表される2つの数値を乗算します

数字が含まれる2つのリンクリストがあるとします。リンクリストによって形成される2つの数値を乗算する必要があります。これは、2つのリンクリストから番号を作成することで簡単に実行できます。例を見てみましょう。

入力

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

出力

2 -> 7 -> 6 -> NULL

アルゴリズム

• 2つのリンクリストを初期化します。
• 2つの変数を0で初期化して、2つの数値を格納します。
• 2つのリンクリストを繰り返し処理します。
  • 最後にあるそれぞれの数値変数に各桁を追加します。
• 結果の数値を乗算し、結果を変数に格納します。
• 結果を含む新しいリストを作成します。
• 新しいリストを印刷します。

実装

以下は、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