Add Two Numbers Represented By Linked Lists Without Recursion, Stack In O(n)

Given two numbers represented by two linked lists, write a function that returns sum list. The sum list is linked list representation of addition of two input numbers. It is not allowed to modify the lists. Also, you cannot use explicit extra space OR stack OR recursion.

Example : 

Input:
  First List: 5->6->3  // represents number 563
  Second List: 8->4->2 //  represents number 842
Output
  Resultant list: 1->4->0->5  // represents number 1405 

This problem was asked in Microsoft Internship Interview at my campus.

The solution for the above problem is available on many websites some of which include geeksforgeeks, stackoverflow , some blogs ,etc. However, the solution that they have given do involves recursion or reversing linked lists and then adding or using stack.

But if we observe carefully , we don't actually need any extra memory in this case . Firstly because we know that the carry in this addition cannot be more than 1. This simplifies things a lot.

Coming  to the algorithm , since we are moving in the reverse direction of addition in this case , we would need to know for every position , the information that will there be any carry from the next position or not . So every position we will evaluate the carry from the next position .

As in the above example : 5 + 8 = 13 , we need to know if the actual answer will be 13 or 14 , and to do that we will see the next node and so on.

Checking this is actually easy as we will keep moving ahead from the node next to the current node and stop once if the sum of the nodes is <= 8 or >= 10. In both these cases , we know the carry , in sum <= 8 , carry is 0 , and if sum >= 10 , carry = 1 . So the only case that will keep us moving is sum = 9. This is because this case is doubtful , we still don't know if there will be carry from the right side.

So by following this , we will come to know for a position if there will be a carry or not . And accordingly we can update our node  , and then update the nodes right to it , which we traversed to know the carry. This way we evaluate whole of the answer. Implementation is a bit tricky and you will need to be careful for handling all the cases.

I implemented the above algorithm in C ,and here is my code .If you find any bugs in the code or algorithm, feel free to comment.

Code : 

struct t_node{

    int data;

    struct t_node *next;

};

typedef struct t_node node;

node* newNode(int data){

    node *t = (node *)malloc(sizeof(node));

    t->data = data;

    t->next = 0;

    return t;

}

node* insert(node *head, int data){

    if(!head){

        return newNode(data);

    }

    else{

        head->next = insert(head->next, data);

        return head;

    }

}

void print(node *head){

    if(head){

        printf("%d ",head->data);

        if(head->next) printf(" -> ");

        print(head->next);

    }

}

node* add(node *h1, node *h2){

    int s = h1->data + h2->data;

    node* ans = 0;

    if(h1->next == 0){

        if(s >= 10) ans = insert(ans,s/10);

        ans = insert(ans,s%10);

        return ans;

    }

    node *head_ans = 0;

    h1 = h1->next , h2 = h2->next;

    while(h1){

        node *t1 = h1, *t2 = h2;

        int l = 0;

        while(t1){

            int sum = t1->data + t2->data;

            if(sum <= 8){

                l = 1;

                break;

            }

            else if(sum >= 10){

                l = 2;

                break;

            }

            t1 = t1->next ;

            t2 = t2->next ;

        }

        if(l == 2) ++s;

        if(head_ans == 0){

            if(s >= 10) ans = insert(ans,s/10);

            ans = insert(ans,s%10);

            head_ans = ans;

            if(s >= 10) ans = ans->next ;

        }

        else{

            ans->data = s;

        }

        node *l1 = h1 , *l2 = h2;

        if(l == 0 || l == 1){

            while(l1){

                int sum = l1->data + l2->data;

                ans->next = newNode(sum);

                ans = ans->next;

                if(l1 == t1) break;

                l1 = l1->next , l2 = l2->next;

            }

            if(!l1) return head_ans;

            else l1 =  l1->next , l2 = l2->next;

        }

        else{

            while(1){

                if(l1 != t1){

                    ans->next = newNode(0);

                    ans = ans->next;

                    l1 = l1->next , l2 = l2->next;

                }

                else{

                    int sum = l1->data + l2->data;

                    ans->next = newNode(sum%10);

                    ans = ans->next;

                    l1 = l1->next , l2 = l2->next;

                    break;

                }

            }

        }

        h1 = l1 , h2 = l2;

        s = ans->data;

    }

    return head_ans;

    ///~

}

int main(){

    int n1, n2, x;

    node *list1, *list2;

    list1 = list2 = 0;

    scanf("%d%d",&n1,&n2);

    while(n1--) scanf("%d",&x), list1=insert(list1, x);

    while(n2--) scanf("%d",&x), list2=insert(list2, x);

    puts("") ;print(list1);

    puts("") ;print(list2);

    puts("");

    node *ans=add(list1,list2);

    print(ans);

    return 0;

}