## Introduction

A linked list is a linear data structure in which the entries are not kept in memory in the same sequence. A pointer connects each link element to the one succeeding it. The structure looks similar to this:

Letâ€™s discuss how we solve this in C++.

### Problem Statement

In this problem, we are given two numbers represented by linked lists. We have to multiply the numbers and display the result.

### Sample Examples

**Example 1:**

```
Input :
Linked List 1: 7 -> 4 -> 9
Linked List 2: 8 -> 3
Output : 62167
Explanation : The product of 749 and 83 is 62167
```

**Example 2:**

```
Input :
Linked List 1: 4 -> 9 -> 5
Linked List 2: 6 -> 1
Output : 30195
Explanation : The product of 495 and 61 is 30195.
```

## Approach

In this approach, we traverse both lists and get the numbers we have to multiply. Then after multiplying them, we return the solution as a list.

Also read - __Merge sort in linked list__

### Steps of Algorithm

- Firstly, we initialise two variables with value zero to store the value of the two linked lists.
- We iterate over the two lists, multiplying their values by ten and adding them to get the value.
- We multiply the two numbers and store the result in a new list.
- This new list is displayed as the answer.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void addNewNode(struct Node** head, int new_val) {
struct Node* newNode = new Node;
newNode->data = new_val;
newNode->next = *head;
*head = newNode;
}
void multiplyLL(struct Node* firstList, struct Node* secList,
struct Node** resultList) {
int no1 = 0, no2 = 0;
while (firstList || secList) {
if (firstList) {
no1 = no1 * 10 + firstList->data;
firstList = firstList->next;
}
if (secList) {
no2 = no2 * 10 + secList->data;
secList = secList->next;
}
}
int result = no1 * no2;
while (result) {
addNewNode(resultList, result % 10);
result /= 10;
}
}
void dispList(struct Node *node) {
while(node != NULL) {
cout<<node->data;
if(node->next)
cout<<"->";
node = node->next;
}
cout << "\n";
}
int main(void) {
struct Node* firstList = NULL;
struct Node* secList = NULL;
addNewNode(&firstList, 5);
addNewNode(&firstList, 9);
addNewNode(&firstList, 4);
dispList(firstList);
addNewNode(&secList, 1);
addNewNode(&secList, 6);
dispList(secList);
struct Node* resultList = NULL;
multiplyLL(firstList, secList, &resultList);
dispList(resultList);
return 0;
}
```

**Output:**

```
4->9->5
6->1
3->0->1->9->5
```

### Complexity Analysis

**Time Complexity:** O(N+M), where N and M are the sizes of the two given linked lists.

**Explanation: **In this approach, the two linked lists determine the time complexity of the program.

**Space Complexity**: O(M+N)

**Explanation: **In this approach, the space required depends on the sizes of the two given linked lists.

Also see, __Rabin Karp Algorithm__