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 ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )