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