# Multiply two numbers represented by Linked Lists

Soumya Deep Sahu
Last Updated: Aug 9, 2022
EASY

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

1. Firstly, we initialise two variables with value zero to store the value of the two linked lists.
2. We iterate over the two lists, multiplying their values by ten and adding them to get the value.
3. We multiply the two numbers and store the result in a new list.
4. 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;
};

struct Node* newNode = new Node;
newNode->data = new_val;
}

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) {
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;

dispList(firstList);

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.

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