Add 2 numbers expressed as singly linked lists

Problem

Add 2 numbers which are expressed as singly linked lists. Results also should be in a linked list.

Solution

• Use recursion to traverse all the way to end and compute sum while returning backwards towards the start.
• Deal with the carry while adding 2 digits.
• Time complexity O(n) where n being the length of one of the lists.
• Assumption – Both the inputs have same number of digits. If not, a preparatory step needs to be included to make sure both the inputs have same number of digits by prepending zeros on the input list which is shorter.
• java based implementation

Abstract singly linked list mechanics.

package com.computepatterns.problemsolving.linkedlist;

/**
 * Abstract implementation of singly linked list
 */
public class AbstractSinglyLinkedList {
    private Node start;

    public void setStart(Node start) {
        this.start = start;
    }

    /**
     * Creates string representing the sequence of the content of the list delimite by coma.
     */
    public String createStringRepresentation(Node start){
        Node currentNode = start;
        StringBuilder toPrint = new StringBuilder();
        while(null != currentNode){
            toPrint.append(currentNode.getValue() + ",");
            currentNode = currentNode.next;
        }
        return toPrint.toString();
    }

    /**
     * Represents nodes in the linked list.
     */
    protected static class Node{
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return value == node.value &&
                    com.google.common.base.Objects.equal(next, node.next);
        }

        @Override
        public int hashCode() {
            return com.google.common.base.Objects.hashCode(value, next);
        }

        public int getValue() {
            return value;
        }

        Node getNext() {
            return next;
        }


        public void setNext(Node next) {
            this.next = next;
        }
    }
}

Solution implementation

package com.computepatterns.problemsolving.linkedlist;

/**
 * Find the sum of 2 numbers represented in 2 linked lists.
 * <p>
 *     Inputs and output to be expressed in singly linked list.
 *     Assume that both the inputs have same number of digits.
 * </p>
 */
public class AdditionLinkedList extends AbstractSinglyLinkedList{
    /* Traversal head of the result */
    private Node resultTraversalHead;

    /**
     * Finds the sum recursively, create the node representing sum of the nodes and add it to result.
     * @param input1
     * @param input2
     * @return Carry if the sum of digits represented by nodes > 9.
     */
    private int findSumRecursively(Node input1, Node input2){

        int carry = 0;

        /* Recurse till the end of both the inputs */
        if(null != input1.getNext() && null != input2.getNext()) {
            carry = findSumRecursively(input1.getNext(), input2.getNext());
        }

        /* Find out sum while coming back from recursion. */
        int sum = input1.getValue() + input2.getValue();

        /* Deal with the carry */
        sum += carry;
        int value = sum;
        if(sum > 9){
            value = sum % 10;
        }

        /* Form result */
        Node currentNode = new Node(value);
        if(null != resultTraversalHead) {
            currentNode.setNext(resultTraversalHead);
        }
        resultTraversalHead = currentNode;

        // Return carry.
        if(sum > 9) {
            return 1;
        }else{
            return 0;
        }
    }

    /**
     * Find the sum of numbers expressed in singly linked list. Both the inputs to have same number of digits.
     * @param input1Start
     * @param input2Start
     * @return Start node of the result.
     */
    public Node findSum(Node input1Start, Node input2Start){
        int carry = findSumRecursively(input1Start, input2Start);
        if(carry > 0){
            Node currentNode = new Node(carry);
            currentNode.setNext(resultTraversalHead);
            resultTraversalHead = currentNode;
        }
        return resultTraversalHead;
    }
}

Unit test

package com.computepatterns.problemsolving.linkedlist;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

/**
 * Testing addition of numbers expressed in singly linked list.
 */
public class AdditionLinkedListTest {

    @Test
    public void testFindSum_noCarry_sameNoOfDigits() throws Exception {
        AdditionLinkedList.Node input1Node1 = new AdditionLinkedList.Node(5);
        AdditionLinkedList.Node input1Node2 = new AdditionLinkedList.Node(6);
        AdditionLinkedList.Node input1Node3 = new AdditionLinkedList.Node(7);

        input1Node1.setNext(input1Node2);
        input1Node2.setNext(input1Node3);

        AdditionLinkedList.Node input2Node1 = new AdditionLinkedList.Node(3);
        AdditionLinkedList.Node input2Node2 = new AdditionLinkedList.Node(2);
        AdditionLinkedList.Node input2Node3 = new AdditionLinkedList.Node(1);

        input2Node1.setNext(input2Node2);
        input2Node2.setNext(input2Node3);

        AdditionLinkedList addition = new AdditionLinkedList();
        String result = addition.createStringRepresentation(addition.findSum(input1Node1, input2Node1));
        assertEquals("8,8,8,", result);
    }

    @Test
    public void testFindSum_withCarry() throws Exception {
        AdditionLinkedList.Node input1Node1 = new AdditionLinkedList.Node(5);
        AdditionLinkedList.Node input1Node2 = new AdditionLinkedList.Node(6);

        input1Node1.setNext(input1Node2);

        AdditionLinkedList.Node input2Node1 = new AdditionLinkedList.Node(7);
        AdditionLinkedList.Node input2Node2 = new AdditionLinkedList.Node(5);

        input2Node1.setNext(input2Node2);

        AdditionLinkedList addition = new AdditionLinkedList();
        String result = addition.createStringRepresentation(addition.findSum(input1Node1, input2Node1));
        assertEquals("1,3,1,", result);
    }
}

Grab the source code here.