# Multiply two numbers represented by Linked Lists

## 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.

### 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.

## Frequently Asked Questions

### Do linked lists have fixed sizes?

The size of linked lists is dynamic; they expand and contract as nodes are added and withdrawn, and they do not require more memory than the number of objects in the collection.

### What are the limitations of linked lists?

The linked list uses up more memory to store the elements than an array because each node of the linked list points to a pointer, which takes up more memory. Traversing the nodes of a linked list is quite difficult. We won't be able to access any node at random in this case.

### How many types of linked lists are there?

There are four main types of linked lists: singly-linked lists, doubly linked lists, circular linked lists and circular doubly-linked lists.

## Conclusion

In conclusion, we discussed how to multiply two numbers represented by linked lists. Then, we discussed the algorithm and complexity of the approach.

Refer to our __guided paths__ on __CodeStudio__ to upskill yourself in __Data Structures and Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, and many more! If you want to test your competency in coding, you may check out the mock __test series__ and participate in the __contests__ hosted on CodeStudio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the __problems__, __interview experiences__, and __interview bundle__ for placement preparations.

Nevertheless, you may consider our paid __courses__ to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!