#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