Monday, September 19, 2011

Sum of two long positive numbers (each represented by linked lists)

Code :

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
 
unsigned char c;
struct Node *next;
 
}Node;
 
 
typedef Node *slist;
 
slist reverse(slist);
Node *makeNode(unsigned char);
 
 
/*
*/
 
slist Sum(slist left, slist right) {
 
if(!left || !right) {
return left ? left : right;
}
 
left = reverse(left);
right = reverse(right);
 
unsigned char carry = left->c + right->c;
 
slist ret = makeNode(carry % 10);
carry /= 10;
 
 
Node *p = left->next;
Node *q = right->next;
Node *r = ret;
 
while(p || q) {
 
carry += (p? p->c : 0)  + (q ? q->c : 0);
 
r->next = makeNode(carry % 10);
carry /= 10;
 
r = r->next;
p = p ? p->next : NULL;
q = q ? q->next : NULL;
}
 
if(carry)
r->next = makeNode(1);
 
reverse(left);
reverse(right);
 
return reverse(ret);
 
}
 
/*
utilities
*/
 
slist reverse(slist s) {
 
if(s->next == NULL)
return s;
 
Node *ret = reverse(s->next);
 
s->next->next = s;
s->next = NULL;
 
return ret;
}
 
Node *makeNode(unsigned char c) {
 
Node * tmp = calloc(sizeof(Node), 1);
 
tmp->c = c;
 
return tmp;
 
}
 
 
void print(slist s) {
 
if(s == NULL) {
printf("\n");
return;
}
printf("%c", s->c + '0');
 
print(s->next);
}
 
 
slist listFromString(const unsigned char *s) {
 
if(!s || !*s) return NULL;
 
slist ret = makeNode(*s++ - '0');
 
Node *tmp = ret;
 
unsigned char c;
 
while((c = *s++)) {
tmp->next = makeNode(c - '0');
tmp = tmp->next;
}
 
return ret;
}
 
int main()
{
slist left  = listFromString("99");
slist right  = listFromString("233823");
 
slist sum = Sum(left, right);
 
print(sum);
return 0;
}

0 comments:

Post a Comment