Add numbers given in the form of Linked List

Two numbers are given in the form of linked list (with each node storing one digit). Write an algorithm which will compute the sum of these two linked lists. The result should be a linked list as below:

Solution:

If you don’t want to read, you can watch the video below:

Method1: Reverse the lists

Algorithm:

Step1: Reverse list1
Step2: Reverse list2
Step3: add list1 & list2 from forward direction
         and keep adding the new element at the front of result list.

For example:

If the original lists are

Num1: 1 -> 2 -> 4
Num2: 1 -> 0 -> 2 -> 3 -> 4

Reversing the lists

Num1: 4 -> 2 -> 1
Num2: 4 -> 3 -> 2 -> 0 -> 1

Adding the lists

Num1: 4 -> 2 -> 1
Num2: 4 -> 3 -> 2 -> 0 -> 1
Sum: 8 -> 5 -> 3 -> 0 -> 1

Reverse the Sum list to get the actual sum:

Sum: 1 -> 0 -> 3 -> 5 -> 8

Note that we don’t need the last step if we keep inserting at the head of the list in the previous step.

Node* addUsingReverse(Node*h1, Node*h2)
{
    reverseLL(&h1);
    reverseLL(&h2);
    Node*a = h1;
    Node*b = h2;
    int carry = 0;
    Node* c = NULL;
    while(a != NULL || b!= NULL)
    {
        int sum = carry;
        if(a != NULL)
            sum += a->data;
        if(b != NULL)
            sum += b->data;
        carry = sum / 10;
        sum = sum % 10;
        appendNode(&c, sum);
        if(a != NULL)
            a = a->link;
        if(b != NULL)
            b = b->link;
    }
    if(carry != 0)
        appendNode(&c, carry);
    reverseLL(&h1);
    reverseLL(&h2);
    reverseLL(&c);
    return c;
}

Helper functions used in the above code (to add Node in the list and reverse the list) are as below:

/**
 * Create a new Node with data = d and append it to the
 * end of the linked list pointed to be *head.
 * Receive Node** because head itself may be null (zero elements in the list)
 */
void appendNode(Node **head, int d)
{
    if(head == NULL)
        return;
    if(*head == NULL)
    {
        *head = new Node(d);
    }
    else
    {
        Node* temp = *head;
        while(temp->link != NULL)
            temp = temp->link;
        temp->link = new Node(d);
    }
}
/**
 * Function to reverse the linked list.
 */
void reverseLL(Node** h)
{
    if(h==NULL || *h == NULL || (*h)->link == NULL)
        return;
    Node* a = (*h);
    Node* b = a->link;
    Node* c = b->link;
    a->link = NULL;
    while(b != NULL)
    {
        b->link = a;
        a = b;
        b = c;
        if(c != NULL)
            c = c->link;
    }
    *h = a;
}

Structure of Node is as Below:

struct Node
{
    int data;
    Node *link;
    Node(int d):data(d),link(NULL){}
};

Note: The code above is a C++ code. You must have noticed the Constructor in the Node struct and the new operator. If you are from C background then please change the code accordingly.

Method 2: using Stacks

This algorithm does not require us to reverse the list. Following are the steps:

Algorithm:

Step1: Push all the nodes of num1 in Stack1
Step2: Push all the nodes of num2 in Stack2
Step3: Keep popping the elements from two stacks and adding them
        and inserting them in the result list at the front of the list.

Code:

Node* addUsingStack(Node* h1, Node* h2)
{
    Stack s1, s2;
    while(h1 != NULL)
    {
        s1.push(h1->data);
        h1=h1->link;
    }
    while(h2 != NULL)
    {
        s2.push(h2->data);
        h2=h2->link;
    }
    int carry = 0;
    Node* c = NULL;
    while(!s1.isEmpty() || !s2.isEmpty())
    {
        int sum = carry;
        if(!s1.isEmpty())
            sum += s1.pop();
        if(!s2.isEmpty())
            sum += s2.pop();
        carry = sum / 10;
        sum = sum % 10;
        addAtFront(&c, sum);
    }
    if(carry != 0)
        addAtFront(&c, carry);
    return c;
}

Function to add Node at the front of the list is very simple:

/** Create a new node and add it in the front of the list represented by head;
 */
void addAtFront(Node **head, int d)
{
    if(head == NULL){ return; } // paranoid check.
    Node *temp = new Node(d);
    temp->link = *head;
    *head = temp;
}

Download the code:
https://bitbucket.org/hikrawat/youtube_code/src/master/Interview%20Questions/Linked%20List/Add%20numbers%20given%20as%20linked%20lists.cpp