Subtration in Linked List
PROBLEM :
Given two linked lists that represent two large positive numbers. Your task is to complete the function SubLinkedList which takes two arguments l1 and l2. The function subtracts the smaller number from larger one and return a pointer to the resultant linked list.
Input
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer n denoting the size of the first linked list (l1) In the next line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list .
Output:
For each test case output will be space separated values of the resultant linked list.
Constraints:
1<=T<=100
1<=n,m<=100
Example:
Input:
1
3
1 0 0
1
1
Output:
0 9 9
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
/* Structure of linked list node
struct node
{
int data;
struct node* next;
}node;
*/
/*You are required to complete this method*/
node* Subtration_Linked_List(node *,node *,bool *) ;
int list_length(node *) ;
node* add_zeros(node *,int ) ;
node* subLinkedList(node* l1, node* l2)
{
if(l1==NULL&&l2==NULL)
return NULL ;
int len1,len2 ;
len1=list_length(l1) ;
len2=list_length(l2) ;
node *slist,*llist ;
llist=NULL ;
slist=NULL ;
if(len1!=len2)
{
llist=len1>len2?l1:l2 ;
slist=len1<len2?l1:l2 ;
slist=add_zeros(slist,abs(len1-len2)) ;
}
else
{
node *temp1,*temp2 ;
temp1=l1 ;
temp2=l2 ;
while(temp1&&temp2)
{
if(temp1->data!=temp2->data)
{
llist=(temp1->data>temp2->data)?l1:l2 ;
slist=(temp1->data<temp2->data)?l1:l2 ;
break ;
}
temp1=temp1->next ;
temp2=temp2->next ;
}
}
bool borrow=false ;
return Subtration_Linked_List(llist,slist,&borrow) ;
}
int list_length(node *head)
{
if(head==NULL)
return 0 ;
node *temp ;
int count=0 ;
temp=head ;
while(temp!=NULL)
{
count++ ;
temp=temp->next ;
}
return count ;
}
node* add_zeros(node *head,int no)
{
node *temp ;
while(no)
{
temp=(node*)malloc(sizeof(node)) ;
temp->data=0 ;
temp->next=head ;
head=temp ;
no-- ;
}
return head ;
}
node* Subtration_Linked_List(node *llist,node *slist,bool *borrow)
{
if(llist==NULL&&slist==NULL&&(*borrow)==false)
return NULL ;
node *prev ;
prev=Subtration_Linked_List(llist->next,slist->next,&(*borrow)) ;
int n1,n2,diff ;
n1=llist->data ;
n2=slist->data ;
if(*borrow)
{
n1-- ;
(*borrow)=false ;
}
if(n1<n2)
{
n1=n1+10 ;
(*borrow)=true ;
}
diff=n1-n2 ;
node *curr ;
curr=(node*)malloc(sizeof(node)) ;
curr->data=diff ;
curr->next=prev ;
return curr ;
}
---------------------------------------------------------------------------------
Given two linked lists that represent two large positive numbers. Your task is to complete the function SubLinkedList which takes two arguments l1 and l2. The function subtracts the smaller number from larger one and return a pointer to the resultant linked list.
Input
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer n denoting the size of the first linked list (l1) In the next line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list .
Output:
For each test case output will be space separated values of the resultant linked list.
Constraints:
1<=T<=100
1<=n,m<=100
Example:
Input:
1
3
1 0 0
1
1
Output:
0 9 9
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
/* Structure of linked list node
struct node
{
int data;
struct node* next;
}node;
*/
/*You are required to complete this method*/
node* Subtration_Linked_List(node *,node *,bool *) ;
int list_length(node *) ;
node* add_zeros(node *,int ) ;
node* subLinkedList(node* l1, node* l2)
{
if(l1==NULL&&l2==NULL)
return NULL ;
int len1,len2 ;
len1=list_length(l1) ;
len2=list_length(l2) ;
node *slist,*llist ;
llist=NULL ;
slist=NULL ;
if(len1!=len2)
{
llist=len1>len2?l1:l2 ;
slist=len1<len2?l1:l2 ;
slist=add_zeros(slist,abs(len1-len2)) ;
}
else
{
node *temp1,*temp2 ;
temp1=l1 ;
temp2=l2 ;
while(temp1&&temp2)
{
if(temp1->data!=temp2->data)
{
llist=(temp1->data>temp2->data)?l1:l2 ;
slist=(temp1->data<temp2->data)?l1:l2 ;
break ;
}
temp1=temp1->next ;
temp2=temp2->next ;
}
}
bool borrow=false ;
return Subtration_Linked_List(llist,slist,&borrow) ;
}
int list_length(node *head)
{
if(head==NULL)
return 0 ;
node *temp ;
int count=0 ;
temp=head ;
while(temp!=NULL)
{
count++ ;
temp=temp->next ;
}
return count ;
}
node* add_zeros(node *head,int no)
{
node *temp ;
while(no)
{
temp=(node*)malloc(sizeof(node)) ;
temp->data=0 ;
temp->next=head ;
head=temp ;
no-- ;
}
return head ;
}
node* Subtration_Linked_List(node *llist,node *slist,bool *borrow)
{
if(llist==NULL&&slist==NULL&&(*borrow)==false)
return NULL ;
node *prev ;
prev=Subtration_Linked_List(llist->next,slist->next,&(*borrow)) ;
int n1,n2,diff ;
n1=llist->data ;
n2=slist->data ;
if(*borrow)
{
n1-- ;
(*borrow)=false ;
}
if(n1<n2)
{
n1=n1+10 ;
(*borrow)=true ;
}
diff=n1-n2 ;
node *curr ;
curr=(node*)malloc(sizeof(node)) ;
curr->data=diff ;
curr->next=prev ;
return curr ;
}
---------------------------------------------------------------------------------
Comments
Post a Comment