About Me

Monday, March 28, 2011

WAP to SumTwo Number Which are represented by node in linked list


#include<stdio.h>
#include<malloc.h>
 
/* Link list node */
struct node
{
int data;
struct node* next;
};
 
/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
 
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
 
/* put in the data */
new_node->data = new_data;
 
/* link the old list off the new node */
new_node->next = (*head_ref); 
 
/* move the head to point to the new node */
(*head_ref) = new_node;
}
 
 
 
struct node* addition (struct node* temp1, struct node* temp2)
{
 
struct node* prev = NULL;
int carry = 0,a,b,result;
 
while (temp1 || temp2) //while both lists exist
{
 
if(temp1) a=temp1->data;
else a=0;
 
if(temp2) b=temp2->data;
else b=0;
 
 
 
 
result = carry;
if(temp1)
result+=temp1->data;
if(temp2)
result+=temp2->data;
 
 
carry=result/10;
 
struct node * newnode = (struct node*) malloc (sizeof(struct node));
newnode->data=(result)%10;
newnode->next = prev;
 
prev=newnode;
if(temp1)
temp1=temp1->next;
if(temp2)
temp2=temp2->next;
}
return prev;
 
}
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
} 
 
/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;
struct node* head1 = NULL;
struct node* head2 = NULL;
 
 
/* Created Linked list is 1->2->3->4->5->6->7->8 */
 
push(&head1, 4);
push(&head1, 3);
push(&head1, 2);
push(&head1, 1);
 
reverse(&head1); 
 
push(&head2, 6);
push(&head2, 5);
push(&head2, 4);
 
reverse(&head2); 
 
head=addition(head1,head2); 
 
 
 
printList(head);
 
return(0);
}

TC O(n+m) where n,m are the number of digits in given numbers.
SC O(1)
Run Here 
https://ideone.com/j4Z8Z

6 comments:

  1. if(carry){
    struct node * newnode = (struct node*) malloc (sizeof(struct node));
    newnode->data=carry;
    newnode->next = prev;

    prev=newnode;
    }

    return prev;

    }

    Add above lines to your addition function (at the end).

    ReplyDelete
  2. @ANAND I THINK solution already contains what u are trying to saying , have a closer look although i used to put the solution after testing for different inputs. still if fails do notify me i will be happy to help :)

    Shashank

    ReplyDelete
  3. https://ideone.com/KWOfc doesnt contains the code for this program

    ReplyDelete
  4. @sreekar , thanks for correction , i have updated the same. also give me some time to revert back to all of your comments

    happy Learning :)

    Shashank

    ReplyDelete
  5. can't we add the numbers and store the result in the bigger of the two lists and send the list as the resultant one? In this way we will not need any extra space.

    ReplyDelete
  6. @jagannath hey number are itself represented by linked list e.g. every node in sll contain a single digit so we have to add two sll ..we don't number in any other way .

    check this how it works

    https://ideone.com/j4Z8Z

    let me know if still anything wrong ?

    Cheers
    Shashank

    ReplyDelete

Hi thanks , we will get back to you shortly !!!