Problem : Given two numbers in the form of linked lists. Get the sum of these two numbers in another linked list.

Hi! This is a common question that you may often encounter in interviews. Having a close look, i found that this question is primarily asked by Amazon during first round of technical (f2f / telephonic) interviews. The question is pretty simple. You have two numbers in the form of linked lists. You wanna add them and store the result in another linked list.

Two approaches :
     (+)  Using Stack
     (+)  Using Recursion
We would go the stack way. Would require O(m+n) space but faster access times. Recursion is a better option when you are concerned with space.

Algorithm :
- start from the lower LSB of both numbers and go on adding.
- maintain a variable for the carry (initialize by 0) and if the sum of any two digits exceeds 9 then extract the msb into the carry variable and place the lsb number on result's place.
- Go on doing this till one or both of the numbers end up.
- Add the remaining digits with the carry (if any) and place them to their respective places.

Time analysis :
 (+) Extracting digits and setting them to their respective places seems to be linear as we shall see.
 (+) O(m+n), where m is the size of first number (length of linked list) and n is of the second number.

SPOILER ALERT :
The following code requires some kind knowledge of using STL library of C++. A simple library that we can use.
Stack and its internal functions can be used by the members of the stack data structure.

#include<iostream>
#include<stack>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

using namespace std;

/**
total complexity = O(m+n)
**/

/*** llist ***/
typedef struct nodej node;
struct nodej
{
    int data;
    struct nodej * next;
};

node * insertNum(int num)
{
    node * temp = (node *)malloc(sizeof(node));
    temp->data = num;
    temp->next = NULL;
    return temp;
}
/*************/

int main()
{
    node *first, *second, *sum;
    node * sum_t=sum;

    /**
    * Given numbers
    * insert them into LL
    **/

    first = insertNum(9);
    first->next = insertNum(1);
    first->next->next = insertNum(3);
    first->next->next->next = insertNum(5);
    second = insertNum(9);
    second->next = insertNum(4);
    second->next->next = insertNum(2);



    stack<int> my1,my2,my3;
    node * temp;
    temp=first;
    /**
    * push the whole linked list into
    * a stack
    **/
    while(temp!=NULL)
    {
        my1.push(temp->data);
        temp = temp->next;
    }

    temp=second;
    while(temp!=NULL)
    {
        my2.push(temp->data);
        temp = temp->next;
    }
    /***********************************/

    /** now solve **/
    int rem=0;
    int a,b,c;

    /**
    * solve by taking top digits, while both exist,
    * and add them with the remainder.
    * if sum>9, extract msb into the remainder and
    * push the lsb into the result stack.
    **/
    while(my2.size()!=0 && my1.size()!=0)
    {
        a=my1.top();
        b=my2.top();
        c=a+b+rem;
        if(c>9)
        {
            rem = c/10;
            c = c%10;
        }
        my1.pop();
        my2.pop();
        my3.push(c);
    }
    /**********************************************/


    /**
    * it may be possible that either of their lengths
    * are greater than the other or not equal.
    * in such a case, add the remaining digits with
    * the remainder from above, extract msb into
    * the remainder and push the lsb into the stack
    **/
    if(my1.size()>0)
    {
        int a;
        while(my1.size()!=0)
        {
            a = my1.top();
            a = a+rem;
            rem = a/10;
            a = a%10;
            my3.push(a);
            my1.pop();
        }
    }
    if(my2.size()>0)
    {
        int a;
        while(my2.size()!=0)
        {
            a = my2.top();
            a = a+rem;
            rem = a/10;
            a = a%10;
            my3.push(a);
            my2.pop();
        }
    }
    /*********************************************/

    /**
    * it is possible that the remainder still
    * goes further into msb than the numbers
    * themselves. hence if there is a remainder
    * which is greater than 0 (obviously), then
    * push to stack
    **/
    if(rem>0)
    {
        my3.push(rem);
    }
    /**********************************************/


    /**
    * now inserting back the stack contents
    * into the linked list.
    **/
    sum = insertNum(my3.top());
    my3.pop();
    sum_t=sum;
    while(my3.size()!=0)
    {
        sum_t->next = insertNum(my3.top());
        sum_t = sum_t->next;
        my3.pop();
    }
    /***********************************************/

    /**
    * printing the result
    **/
    sum_t=sum;
    while(sum_t!=NULL)
    {
        cout<<sum_t->data<<" ";
        sum_t = sum_t->next;
    }
    cout<<endl;

    return 0;
}

So this was way I thought it could be done using stack. However if you are cheesy on space then do proceed for the recursive code. Its process is similar to the above with some modifications in coding style. Any suggestions or pointing out errors would be really helpful (to me and to others).