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