# Multiply two numbers represented by linked lists ?

+7 votes
3,322 views

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046

posted Oct 29, 2013
Share this question

## 2 Answers

+1 vote

5->6->3 Multiplied by 8->4->2

Normal Multiplication:

``````      563
*  842
---------------
1126
2252
4504
----------------
474046
----------------
``````

Now reverse both linked lists to access digits from right side..
3->6->5 , 2->4->8
Now multiply 3->6->5 with 2 we get
3*2 = 6, 6*2 = 12, 5*2 = 10
if number is not one digit then store it in carry add it to next number i.e,
after multiplying
3->6->5 with 2 ===> 6, carry = 0.
3->6->5 with 2 ===> 6->2, carry = 1.
3->6->5 with 2 ===> 6->2->1, carry = 1.
3->6->5 with 2 ===> 6->2->1->1, carry = 0.
Final result after multiplying single digit is 6->2->1->1
similarly 3->6->5 with 4 is 2->5->2->2
Now add the above two one directly and other with adding a single 0 at starting i.e, 6->2->1->1 + 0->2->5->2->2 = 6->4->6->3->2
Now again multiply 3->6->5 with 8 is 4->0->5->4 and add two 0's at starting so it will become 0->0->4->0->5->4

result will be 6->4->6->3->2 + 0->0->4->0->5->4 = 6->4->0->4->7->4
Now reverse that you will get final result : 4->7->4->0->4->6

Here i am not mentioning about add linked lists we can do it by using carry..and i hope you will understand about shifting zeros if not do comment..

answer Nov 25, 2013 by
0 votes
``````#include<iostream>
#include<bits/stdc++.h>
using namespace std;

struct node1
{
int data;
struct node1 *next;
};
typedef struct node1 node;

node * create_node(int data)
{
node * head=(node *)malloc(sizeof(node));
head->data=data;
head->next=NULL;
return head;
}

int get_length(node *head)
{
int counter=0;
while(head!=NULL)
{
head=head->next;
counter++;
}
return counter;
}

node *get_linklist(void)
{
node *temp,*head;
head=NULL;
temp=head;
int counter=0;
int data;
do
{
counter++;
cin>>data;
if(data!=-1)
{
if(head==NULL)
{
head=create_node(data);
temp=head;
}
else
{
temp->next=create_node(data);
temp=temp->next;
}
}
}while(data!=-1);
return head;
}

void print_linklist(node *head)
{
while(head!=NULL)
{
cout<<head->data<<" ";
head=head->next;
}
cout<<endl;
}

void multiply_node(node *num1,node *num2, node *t_num,int *carry)
{
int sume;
if(num1->next==NULL)
{
sume= (num1->data) * (num2->data) + (*carry);
t_num->data=sume%10;
*carry=sume/10;
}
else
{
multiply_node(num1->next,num2,t_num->next,carry);
sume= (num1->data) * (num2->data) + (*carry);
t_num->data=sume%10;
*carry=sume/10;
}
}

void add_me(int n1,int n2,node *t_num1,node *t_num2,int *carry,node **t_sum)
{
int sum;
if(n1==n2)
{
if(n1==1)
{
sum=t_num1->data + t_num2->data + (*carry);
t_num2->data=sum%10;
*carry=sum/10;
return;
}
else
{
add_me(n1-1,n2-1,t_num1->next,t_num2->next,carry,t_sum);
sum=t_num1->data + t_num2->data + (*carry);
t_num2->data=sum%10;
*carry=sum/10;
return;
}
}
else if(n1>n2)
{
add_me(n1-1,n2,t_num1->next,t_num2,carry,t_sum);
sum=t_num1->data+(*carry);
node *temp=create_node(sum%10);
temp->next=(*t_sum);
(*t_sum)=temp;
*carry=sum/10;
}
}

void add_linklist(node *t_num,node **t_sum)
{
int len1=get_length(t_num);
int len2=get_length(*t_sum);
int carry=0;
add_me(len1,len2,t_num,*t_sum,&carry,t_sum);
if(carry)
{
node *temp=create_node(carry);
temp->next=(*t_sum);
(*t_sum)=temp;
}
}

node *add_temp(node *t_num,int gap,node **t_sum)
{
node *dev,*temp;
if(gap==0)
{
while(t_num!=NULL)
{
if((*t_sum)==NULL)
{
(*t_sum)=create_node(t_num->data);
dev=(*t_sum);
}
else
{
dev->next=create_node(t_num->data);
dev=dev->next;
}
t_num=t_num->next;
}
}
else
{
int len=get_length(*t_sum);
int i=0;
dev=(*t_sum);
while(i<len-gap-1)
{
dev=dev->next;
i++;
}
temp=dev->next;
dev->next=NULL;
add_linklist(t_num,t_sum);
dev->next=temp;
}
}

void multiply_linklist(node *num1,node *num2,node *t_num,int *gap,node **t_sum)
{
node *temp;
int carry=0;
if(num2->next==NULL)
{
multiply_node(num1,num2,t_num->next,&carry);

if(carry)
t_num->data=carry;
else
t_num->data=0;
if(t_num->data==0)
{
add_temp(t_num->next,*gap,t_sum);
}
else
{
add_temp(t_num,*gap,t_sum);
}
(*gap)++;

}
else
{
multiply_linklist(num1,num2->next,t_num,gap,t_sum);
multiply_node(num1,num2,t_num->next,&carry);
if(carry)
t_num->data=carry;
else
t_num->data=0;
if(t_num->data==0)
{
add_temp(t_num->next,*gap,t_sum);
}
else
{
add_temp(t_num,*gap,t_sum);
}
(*gap)++;
}
}

int main()
{
node *num1,*num2,*temp,*t_sum,*t_num,*temp1;
num1=get_linklist();
num2=get_linklist();
t_num=NULL;
t_sum=NULL;
node *head1=num1;
while(head1!=NULL)
{
if(t_num==NULL)
{
t_num=create_node(0);
temp1=t_num;
}
else
{
temp1->next=create_node(0);
temp1=temp1->next;
}
head1=head1->next;
}
temp1->next=create_node(0);

int gap=0;
cout<<"Number 1"<<endl;
print_linklist(num1);
cout<<"Number 2"<<endl;
print_linklist(num2);
cout<<"Multiplication"<<endl;
multiply_linklist(num1,num2,t_num,&gap,&t_sum);
print_linklist(t_sum);
return 0;
}
``````
answer Jul 22, 2015 by anonymous
Similar Questions
+2 votes

Result should be stored in new linked list.

+2 votes

Provide an algorithm to add and multiply two large integers which cannot be represented by built-in types, C code would be a great help?

+3 votes

Can someone help me with algo and code?