Addition of Linked Lists

The numbers are represented in linked-list with each node representing a
digit of the number as follows:

1→2→3→ø
9→9→9→ø

Write a C program to add two numbers.

9→9→9→ø
    1→ø
—————————
1→0→0→0→ø

Answer:

struct Node
{
    Node* next;
    int val; 
};

Solution I:

/* Recursive solution */
Node* AddLinkedLists(Node* A, Node* B, size_t *carry)
{
    Node *next_node = NULL;
    if ( A->next )
         A = A->next;
    if ( B->next )
        B = B->next;
    if( (A->next) && (B->next) )
    {
        next_node = AddLinkedList(A,B);
    }
    Node* new_node = new Node();
    int sum = A->val + B->val + *carry
    new_node->val = sum%10 ;
    *carry = sum/10;
    new_node->next = next_node;
    return new_node;
}

Complexity: Space : O(n) , Time : O(n)

Solution II:

1. Reverse the lists O(n)
2. Add the lists
3. Reverse the lists O(n)

Better solution, time : O(n), space : O(1)