Add Two Numbers Represented by Linked Lists

In this article, we will discuss how two numbers represented as linked lists can be added together and store the result in a new linked list. This is a very popular interview question and is also asked as to find the sum of two singly-linked lists. We will be using Java to implement this algorithm.

The sum of two linked lists can be found either in an iterative way or recursive way. In this article, we will discuss the recursive way and in the next article, we will discuss the iterative approach. With the iterative approach, we first need to reverse the list and then find the sum and again the resultant linked list is reversed to get the final result. Hence, the original list is modified.

But if there is a restriction on modifying the list then there is no way to use the iterative approach and recursive approach needs to be implemented.

Problem Statement

Let us discuss the problem statement first. Given a number 56389 and 84231 which can be represented as a linked list as per the below diagram.

The sum of given numbers would be 140620 and this can be represented as:

If you will see closely, the carry i.e. 1 after adding 9 and 1 is to be remembered while moving forward to calculate the sum of next set of nodes because each node can accommodate only 1 bit i.e. from 0 to 9. And that is the reason, the resultant linked list has 6 nodes whereas the source lists have 5 nodes.

Other situations could be the source lists may have an unequal number of nodes. In that case, first, a balancing of the nodes might be required before we start the sum. Our implementation should handle all these scenarios.

Algorithm to Find the Sum

• First find the length of each source linked lists and calculate the difference(d) in the length.
• Next skip d number of nodes and invoke the findSum method which will recursively traverse to the end of the lists.
• Now, find the sum of each nodes
• calculate the carry and the value. Use this value to create a new node whose next pointer will point to the existing node of our result list.
• Return the carry.
• Now, calculate the sum of d nodes which we skipped initially.
• If carry > 0 then create a new node with value as the carry and this new node next pointer will point to the existing node of our result list

Linked List Node Implementation

Now, let us implement our linked list node representation in Java.

public class Node {

    private int data;
    private Node nextNode;

//setters and getters

Algorithm Implementation

A global linked list node is defined to represent the sum. Once the length is found, we have 3 conditions for an equal and unequal number of nodes. The source list with a greater number of nodes is passed as first argument to the private method findSum.

This method traverses to the end of the list and performs the sum. From each recursive call, the carry is returned to the next caller.

Node node = null;

    public Node findSum(Node first, Node second){
        int length1 = findLength(first);
        int length2 = findLength(second);
        //assume both length > 0
        int diff = length1 - length2;
        int carry;
        if (diff < 0){
            carry = findSum(second, first, -diff);
            carry = findRestSum(second, carry, -diff);
        }else if (diff > 0){
            carry = findSum(first, second, diff);
            carry = findRestSum(first, carry, diff);
        }else {
            carry = findSum(first, second, diff);
        }
        if (carry > 0){
            Node currentNode = new Node(carry);
            currentNode.setNextNode(node);
            node = currentNode;
        }
        return node;
    }

    private int findSum(Node first, Node second, int diff){
        //assume diff = 0
        if (diff != 0){
            while (diff != 0){
                first = first.getNextNode();
                diff = diff - 1;
            }
        }
        if (first == null || second == null){
            return 0;
        }
        int c = findSum(first.getNextNode(), second.getNextNode(), diff);
        int sum = first.getData() + second.getData() + c;
        int carry = sum / 10;
        int value = sum % 10;
        Node currentNode = new Node(value);
        currentNode.setNextNode(node);
        node = currentNode;
        return carry;
    }

    private int findRestSum(Node first, int carry, int diff) {
        if (diff == 0){
            return carry;
        }
        int c = findRestSum(first.getNextNode(), carry, diff - 1);
        int sum = first.getData() + c;
        carry = sum / 10;
        int value = sum % 10;
        Node currentNode = new Node(value);
        currentNode.setNextNode(node);
        node = currentNode;
        return carry;
    }

findRestSum() calculates the sum of d nodes. First it traverses to the d node and the it performs the sum.

Runner Class Implementation

It constructs 2 source linked lists and invokes the findSum().

public class LinkedListRunner {

    public static void main(String [] args){
        CustomLinkedList customLinkedList = new CustomLinkedList();
        customLinkedList.insert(5);
        customLinkedList.insert(6);
        customLinkedList.insert(3);
        customLinkedList.insert(8);
        customLinkedList.insert(9);

        customLinkedList.display();


        CustomLinkedList customLinkedList1 = new CustomLinkedList();
        customLinkedList1.insert(8);
        customLinkedList1.insert(4);
        customLinkedList1.insert(2);
        customLinkedList1.insert(3);
        customLinkedList1.insert(1);
        customLinkedList1.display();

        Node result = customLinkedList.findSum(customLinkedList.get(), customLinkedList1.get());
        Node sumHead = result;
        while (sumHead != null){
            System.out.print(sumHead.getData() + " ");
            sumHead = sumHead.getNextNode();
        }
    }
}

  5 6 3 8 9
  8 4 2 3 1
1 4 0 6 2 0 

Conclusion

In this article, we discussed how two numbers represented as linked lists can be added together and store the result in a new linked list in Java.