#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

typedef Node* pNode;

void print(Node * head)
{
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        while(head->next != nullptr) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
        }
        delete head;
    }
}

pNode add(pNode a, pNode b)
{
    pNode head{}, sum{};
    int c(0);
    
    while (a != nullptr || b != nullptr || c != 0) {
        int s(0);
        if (a != nullptr) {
            s += a->data;
            a = a->next;
        }
        if (b != nullptr) {
            s += b->data;
            b = b->next;
        }
        s += c;
        c = s/10;
        s %= 10;
        pNode t = new Node(s, nullptr);
        if (head == nullptr) {
            head = t;
            sum = head;
        } else {
            sum->next = t;
            sum = sum->next;
        }
    }
    
    return head;
}

unsigned len(pNode head)
{
    unsigned l{};
    while (head != nullptr) {
        l++;
        head=head->next;
    }
    return l;
}

pNode padZero(pNode head, unsigned zeros)
{
    for(; zeros != 0; zeros--) {
        head = new Node(0, head);
    }
    return head;
}

pNode doAdd(pNode a, pNode b, int &c)
{
    if (a->next == nullptr && b->next == nullptr) {
        c = (a->data + b->data)/10;
        return new Node((a->data + b->data)%10, nullptr);
    }
    pNode p = doAdd(a->next, b->next, c);
    int d = a->data + b->data + c;
    c = d/10;
    d %= 10;
    return new Node(d, p);
}

pNode add2(pNode a, pNode b)
{
    unsigned la = len(a);
    unsigned lb = len(b);
    if (a < b) a = padZero(a, lb-la);
    else if (a > b) b = padZero(b, la-lb);
    int c(0);
    pNode p = doAdd(a, b, c);
    if (c != 0)
        p = new Node(c, p);
    return p;
}

int main(int argc, char *argv[])
{
    Node *a = new Node(7, new Node(1, new Node(6, nullptr)));
    Node *b = new Node(9, new Node(5 ,new Node(9, new Node(9, nullptr))));
    print(a);
    print(b);
    pNode sum = add(a, b);
    print(sum);
    clear(sum);
    sum = add2(a, b);
    print(sum);
    clear(a);
    clear(b);
    clear(sum);
    return 0;
}