### Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

We will be given two numbers in the form of a linked list, and we need to return a third list that will be the product of both the given lists.

### Problem Statement Understanding

Let's try to understand the problem with the help of an example:

If the linked lists given to us be **list1 = 2â†’3â†’5â†’NULL** and **list2 = 1â†’4â†’NULL**.

- In numeric form,
**list1 = 2â†’3â†’5â†’NULL**can be represented as**235**and**list2 = 1â†’4â†’NULL**can be represented as**14**. - So, according to the problem statement, we need to multiply the given linked lists, i.e., find the product of the numeric form of list1 and list2, and return the product in the form of a linked list.
- The output list will be
**3â†’2â†’9â†’0â†’NULL**, because the product of the numeric form of list1 and list2 is **235*14 = 3290**.

Letâ€™s take another example. If the linked lists given to us be **list1 = 6â†’7â†’4â†’NULL** and **list2 = 2â†’9â†’5â†’NULL**.

- In this case, the numeric form of list1 will be
**674**, and list2 will be**295**. So, our output will be the linked list representation of **674*295 = 198830**, which will be**1â†’9â†’8â†’8â†’3â†’0â†’NULL**.

##### Some more examples

Sample Input 1:

- list1: 1â†’3â†’5â†’NULL
- list2: 2â†’3â†’4â†’NULL

Sample Output 1: 3â†’1â†’5â†’9â†’0â†’NULL

Sample Output 2:

- list1: 1â†’6â†’4â†’8â†’NULL
- list2: 1â†’2â†’3â†’4â†’NULL

Sample Output 2: 2â†’0â†’3â†’3â†’6â†’3â†’2â†’NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letâ€™s move to the approach section.

### Approach

- The input list given to us will contain the most significant digit as the head and the least significant as the last node.
- We know that, for multiplication, we need to start multiplying the digit from the least significant digit to the most significant one.
- We cannot traverse backward in the list so, first, we need to reverse both the lists.
- Now, we will multiply each digit of the second list one by one with a complete first list (just as we do a normal multiplication on pen-paper).
- We will multiply the first digit of the second list with the complete first list and save it to use afterwards.
- Then, we will multiply the second digit of the second list with the complete first list and add this list with the previously obtained list by shifting the elements of this list by one place to the right.
- We will repeat the above steps of multiplication of digits of second list with the complete first list until we reach the second list's end.
- Remember to take care of carry while doing addition and multiplication.
- Finally, we will reverse the obtained list and return it.

### Algorithm

- Reverse both the linked lists.
- Create a
**dummy node**with a value of -1 and name it as**ans**. Also, initialize a pointer**ans_itr**with the address of the dummy node and a pointer**l2_itr**with the head of the second list. - Now, run a while loop till
**l2_itr**is not NULL. - Create a
**head**pointer that will call**multiplyLinkedListWithDigit**function with**l1**and**l2_itr->data**as parameters. (This function will multiply the single digit of the second listâ€™s node with the complete first list). - Now, control moves to
**multiplyLinkedListWithDigit function**:- Create a
**dummy node**with a value of -1 and name it**head**. Also, initialize a pointer named**curr**with it and an integer variable**carry**with zero. - Run a while loop till
**l1**is not NULL or carry is non-zero. - Calculate the
**sum**variable as the sum of**carry**and If**l1**is not NULL, then the product of**digit**and**l1->data**. - Now, update
**carry**by removing the last digit from the**sum**by doing**sum/10**. - Update
**sum**as the last digit of sum, i.e.,**sum %= 10**. - Create a new node with the value of sum and attach it after the
**curr**node. - If
**l1**is not NULL, advance**l1**by a node - Advance
**curr**pointer by one node. - After execution of the while loop, return
**head->next**as the head was the dummy node created initially.

- Create a
- Now, advance the
**l2_itr**to the next node for further multiplication. - Update the
**ans_itr**function by calling the**addTwoLinkedList function**with**ans_itr**and**head**as parameters. - Now the control moves to
**addTwoLinkedList function**:- Initialize a
**prev**pointer with the head of the first list and an integer variable**carry**with zero. - Run a while loop till
**l2**is not NULL or**carry**is non-zero. - Calculate
**sum**by adding**carry**,**prev->next->data**if**prev->next**is not NULL and**l2->data**if l2 is not NULL. - Now, update
**carry**by removing the last digit from the**sum**by doing**sum/10**. - Update
**sum**as the last digit of**sum**i.e.,**sum %= 10**. - Check if
**prev->next**is NULL or not. - If it is not NULL then, assign
**sum**value to**prev->next->data**. - Else, create a new node with
**sum**value and attach it after**prev**. - If
**l2**is not NULL, advance**l2**by one node. - Advance
**prev**by one node. - After execution of the loop, return
**l1**.

- Initialize a
- Advance
**ans_itr**by one node. - After completion of the while loop, advance
**ans**by one node, as**ans**was a dummy node created initially. - Now, reverse the list having
**ans**as head and return it.

**Note:** To understand the algorithm better, follow along with code.

### Dry Run

### Code Implementation

#includeusing namespace std; class Node { public: int data; Node* next; // constructor Node(int x){ data = x; next = NULL; } }; // This function prints the data of a given list void print(Node* head) { Node* curr = head; while (curr != NULL) { cout << curr->data << " -> "; curr = curr->next; } cout<<"NULL"; } // This function will reverse a given list Node* reverse(Node *head) { Node *prev = NULL, *current = head, *next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } // This function will add two lists and it also shifts the // second list by one place while adding and then returns the // result in a third list Node* addTwoLinkedList(Node *l1, Node *l2) { Node *prev = l1; int carry = 0; while (l2 != NULL || carry != 0) { int sum = carry + (prev->next != NULL ? prev->next->data : 0) + (l2 != NULL ? l2->data : 0); carry = sum / 10; sum = sum % 10; if (prev->next != NULL) prev->next->data = sum; else prev->next = new Node(sum); if (l2 != NULL) l2 = l2->next; prev = prev->next; } return l1; } // This function multiplies a linked list with an integer and // returns the result of multiplication as a list Node* multiplyLinkedListWithDigit(Node* l1, int digit) { Node* head = new Node(-1); // dummy node Node* curr = head; int carry = 0; while (l1 != NULL || carry != 0) { int sum = carry + (l1 != NULL ? (l1->data * digit) : 0); carry = sum / 10; sum = sum % 10; curr->next = new Node(sum); if (l1 != NULL) l1 = l1->next; curr = curr->next; } return head->next; } // This function will multiply two linked lists and return // a third list which will be having the result of // multiplication Node* multiplyTwoLL(Node* l1, Node* l2) { l1 = reverse(l1); l2 = reverse(l2); Node* ans = new Node(-1); // dummy node Node* ans_itr = ans; Node* l2_itr = l2; while (l2_itr != NULL) { Node* head = multiplyLinkedListWithDigit(l1, l2_itr->data); l2_itr = l2_itr->next; ans_itr = addTwoLinkedList(ans_itr,head); ans_itr = ans_itr->next; } ans = ans->next; return reverse(ans); } int main(){ Node *list1 = new Node(2); list1->next = new Node(3); list1->next->next = new Node(5); Node *list2 = new Node(1); list2->next = new Node(4); cout<<"Linked list obtained by multiplying list1 and list2: "<

### Output

Linked list obtained by multiplying list1 and list2:

3 -> 2 -> 9 -> 0 -> NULL

**Time Complexity:** O(N*M), where N and M are the numbers of nodes in the linked list 1 and 2.

**Space Complexity:** O(X), where X will be the number of nodes in the resultant list.

So, in this blog, we have tried to explain how you can multiply two linked lists in the most optimal way. This is one of the good problems that helps you strengthen your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).