Multiply two Linked List - Data Structure

Problem Statement:

Given two numbers represented by linked lists, return the multiplication of these two linked lists.

Examples:

Example 1:
Input: L1 = 1->2->3->null , L2= 5->6->null
Output: 6888
Explanation: 123*56=6888

Example 2:
Input: L1 = 1->3 , L2= 2->null
Output: 26
Explanation: 13*2=26

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Since we need the nos. to multiply, we will convert each linked list into the corresponding number it is representing. For ex: 1->2->3 will be 123.

Let’s say we are given 1->2->3 and 5->6

To convert 1->2->3, we will start traversing from the head of the linked list, cur=head. We will take a variable n1=0, and update n1=n1*10+cur->value. We keep moving cur till it reaches null.

Initially , n1=0*10+1 = 1
	n1=1*10+2=12
	n1=12*10+3=123
Similarly for 5->6 . 
Return 123*56 as answer.

Code:

C++ Code

#include<iostream>
using namespace std;
typedef struct Node{
	int data;
	struct Node *next;
}node;

node* createNode(int data,node* start){
	node *p=new node();
	p->data=data;
	p->next=NULL;
	node *temp=start;
	if(start==NULL){
		start=p;
		start->next=NULL;
	}else{
		while(temp->next!=NULL){
			temp=temp->next;
		}
		temp->next=p;
	}
	return start;
}
void printNode(node* s){
	node *p=s;
	while(p!=NULL){
		cout<<p->data;
		if(p->next !=NULL)cout<<"->";
		p=p->next;
	}
}
int multiply(node*head1,node*head2){
	node*p=head1;
	int x=0,y=0;
	while(p!=NULL){
		x=x*10+p->data;
		p=p->next;
	}
	p=head2;
		while(p!=NULL){
		y=y*10+p->data;
		p=p->next;
	}
	return x*y;
}
int main(){
	node*head1=NULL;
	head1 = createNode(2,head1);
	head1 = createNode(1,head1);
	head1 = createNode(5,head1);
	node* head2=NULL;
	head2 = createNode(1,head2);
	head2 = createNode(2,head2);
	
	cout<<"LinkList 1"<<endl;
	printNode(head1);
	cout<<"\nLinkList 2"<<endl;
	printNode(head2);
	cout<<endl;
	int ans = multiply(head1,head2);
	cout<<"Multiplication is : "<<ans;
}

Output:

LinkList 1
2->1->5
LinkList 2
1->2
Multiplication is: 2580

Time Complexity: O(n)

Space Complexity: O(n)+O(m) //n is length of list1, m is length of list 2

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article