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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s