Last Updated on November 28, 2022 by Prepbytes

In this article we will learn an interesting problem of a linked list “multiply two linked lists”. We have given two linked lists and we have to perform the multiplication and return the head of the new list.

## How to multiply two linked lists

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.

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 of multiply two linked lists

- 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 of multiply two linked lists

- 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 of multiply two linked lists

## Code Implementation of multiply two linked lists

#include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; int getCount(struct Node* head); int _getIntesectionNode(int d, struct Node* head1, struct Node* head2); int getIntesectionNode(struct Node* head1, struct Node* head2) { int c1 = getCount(head1); int c2 = getCount(head2); int d; if (c1 > c2) { d = c1 - c2; return _getIntesectionNode(d, head1, head2); } else { d = c2 - c1; return _getIntesectionNode(d, head2, head1); } } int _getIntesectionNode(int d, struct Node* head1, struct Node* head2) { int i; struct Node* current1 = head1; struct Node* current2 = head2; for (i = 0; i < d; i++) { if (current1 == NULL) { return -1; } current1 = current1->next; } while (current1 != NULL && current2 != NULL) { if (current1 == current2) return current1->data; current1 = current1->next; current2 = current2->next; } return -1; } int getCount(struct Node* head) { struct Node* current = head; int count = 0; while (current != NULL) { count++; current = current->next; } return count; } int main() { struct Node* newNode; struct Node* head1 = (struct Node*)malloc(sizeof(struct Node)); head1->data = 10; struct Node* head2 = (struct Node*)malloc(sizeof(struct Node)); head2->data = 3; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 6; head2->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 9; head2->next->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 15; head1->next = newNode; head2->next->next->next = newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = 30; head1->next->next = newNode; head1->next->next->next = NULL; printf("\n The node of intersection is %d \n", getIntesectionNode(head1, head2)); getchar(); }

#include<bits/stdc++.h> using 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: "<<endl; print(multiplyTwoLL(list1,list2)); }

class Node { int data; Node next; Node(int data) { this.data=data; } } class Multiply { static void print(Node head) { Node curr=head; while(curr!=null) { System.out.print(curr.data+"->"); curr=curr.next; } System.out.println("NULL"); } static 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; } static 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; } static Node multiplyLinkedListWithDigit(Node l1,int digit) { Node head=new Node(-1); 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; } static Node multiplyTwoLL(Node l1,Node l2) { l1=reverse(l1); l2=reverse(l2); Node ans=new Node(-1); 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); } public static void main(String[] args) { 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); System.out.println("LinkedList obtained by multiplying list 1 and list 2 :"); print(multiplyTwoLL(list1, list2)); } }

Output

Linked list obtained by multiplying list1 and list2:

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

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

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

**Conclusion**

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 help you strengthen your concepts in LinkedList and if you want to practice more such problems, you can check out Prepbytes (Linked List).

## FAQs related to multiply two linked lists

**1. How do you multiply two linked lists?**

We will multiply two linked lists:

– Initialize a variable to 0.

– Start traversing the linked list.

– Assign the value of the first node to the new variable.

– From the second node, multiply the variable by 10 and also take the modulus of this value by 10^9+7 and then add the value of the node to this variable.

**2. What is the multiple-linked list?**

Multilevel Linked List is a 2D data structure that comprises several linked lists and each node in a multilevel linked list has a next and child pointer. All the elements are linked using pointers.

**3. What is a doubly linked list?**

A doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence.