Given two linked lists, both represent a number need to find its sum linked list.

As described in problem statement, we have two linked lists represents as decimal numbers. We aim to find its sum as a linked list. Let us understand this with an example.

We have to sum 527 + 999584 which is equal to 1000111.

We can solve this problem in two different ways.

  1. Digit by digit sum calculation.
  2. Converting a list to the number and calculate the sum and switch back to the linked list.

Here in this article, we only solve using the first approach, as the second approach is a very straight forward way to solve this problem.

Digit by digit sum calculation

Here we add digits by digits in each node and we pass the carry to its respective previous nodes sum. We do this process until all digits processes. Finally we get the sum linked list. Algorithm for this approach is as follows.

Algorithm

  1. We move both nodes till any one of them reaches to its end.
  2. If both nodes at the current position are null, then the sizes of those two nodes are equal.
    1. If both lists size is the same, then we recursively calculate the sum of the digits while backtracking, still if we left with a carry. We create a node with that data then prepend that node to our result list.
    2. If the original list size is higher, then we move the position until it left with the second list size. We prepend the extra nodes by adding carry to it.
    3. The second list size is higher then we move that until it left with original list size, do the same as in the second step.
Adds the lists with similar length size and brings the carry to its previous lengthy nodes. Here in this example carry 1 adds up to list 999 which gives 1000 which prepends to 111.

Let us jump into the code for this approach.

// Sum if both lists size is equal.
// @result -- output list.
// returns carry.
int findSumLinkedListNums(Node *head1, Node *head2, Node **result)
{
    if (head1 == NULL)
    {
        return 0;
    }
    int sum = head1->data + head2->data;
    int div = findSumLinkedListNums(head1->next, head2->next, result);
    sum = sum + div;
    Node *tmp = new Node(sum % 10);
    tmp->next = *result;
    *result = tmp;
    return (sum / 10);
}

// Adds carry to a linked list using backtracking.
// Output -- carry stores in "div"
void addDividend(Node *head, int *div)
{
    if (head == NULL)
    {
        return;
    }
    if (*div == 0)
    {
        return;
    }
    addDividend(head->next, div);
    int sum = head->data + *div;
    head->data = sum % 10;
    *div = sum / 10;
}

// Gets the sum linked list.
// returns resultant linked list.
Node *getSumLinkedLists(Node *head1, Node *head2)
{
    Node *result = NULL;
    Node *sum = NULL;
    Node *curr1 = head1;
    Node *curr2 = head2;
    while (curr1 && curr2)
    {
        curr1 = curr1->next;
        curr2 = curr2->next;
    }
    if (curr1 == NULL && curr2 == NULL)
    {
        int res = findSumLinkedListNums(head1, head2, &result);
        if (res != 0)
        {
            Node *tmp = new Node(res);
            tmp->next = result;
            result = tmp;
        }
        return result;
    }
    if (curr1 == NULL)
    {
        Node *tmp = head2->next;
        sum = new Node(head2->data);
        Node *prev = sum;
        while (curr2->next)
        {
            prev->next = new Node(tmp->data);
            prev = prev->next;
            tmp = tmp->next;
            curr2 = curr2->next;
        }
        int res = findSumLinkedListNums(head1, tmp, &result);
        if (res != 0)
        {
            addDividend(sum, &res);
            if (res != 0)
            {
                tmp = new Node(res);
                tmp->next = sum;
                sum = tmp;
            }
        }
        prev->next = result;
        return sum;
    }
    else
    {
        Node *tmp = head1->next;
        sum = new Node(head1->data);
        Node *prev = sum;
        while (curr1->next)
        {
            prev->next = new Node(tmp->data);
            prev = prev->next;
            tmp = tmp->next;
            curr1 = curr1->next;
        }
        int res = findSumLinkedListNums(tmp, head2, &result);
        if (res != 0)
        {
            addDividend(sum, &res);
            if (res != 0)
            {
                tmp = new Node(res);
                tmp->next = sum;
                sum = tmp;
            }
        }
        prev->next = result;
        return sum;
    }
}

The complexity of this solution is O(N), where N is the length of the most extended linked list with a constant space. Let us see the complete executable code with the main function.

// Output
1000111

It is all about finding the sum linked list with given two linked lists represents as integers. Please try to solve this problem with the other approach and let our readers know by commenting here below. Happy Learning!.

Advertisements