Multiply Linked Lists

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 *23514 = 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 *674295 = 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.
• 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.
• 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.