#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
6 comments :
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).
@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
https://ideone.com/KWOfc doesnt contains the code for this program
@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
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.
@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
Post a Comment