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 :

anandiiita said...

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).

Unknown said...

@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

sreekar said...

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

Unknown said...

@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

jagannath said...

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.

Unknown said...

@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