Add two numbers represented by linked lists

Question

I've just encountered this question and am trying to solve it using Java.

Here is my solution to it, which may not be optimized or might not be right way to do it. Someone please review whether it is correct or there is some good way to do it. For focusing on logic, I have hard coded List creation and code repetition is present.

package linkedlist.singly;

//Add two numbers represented by linked lists 
// 245   :  5 -> 4 -> 2
// 99789 :  9 -> 8 -> 7 -> 9 -> 9
// Ans   :  99341
public class Add2NumbersInLinkListType2 {

    static int carry=0;

    public static void main(String[] args) {

        Node templ11 = new Node(5);
        Node templ12 = new Node(4);
        Node templ13 = new Node(2);

        Node templ21 = new Node(9);
        Node templ22 = new Node(8);
        Node templ23 = new Node(7);
        Node templ24 = new Node(9);
        Node templ25 = new Node(9);

        templ11.setNext(templ12);
        templ12.setNext(templ13);

        templ21.setNext(templ22);
        templ22.setNext(templ23);
        templ23.setNext(templ24);
        templ24.setNext(templ25);

        Node res = findSum(templ11, templ21, 0);
        if(carry==1){
            Node tempNode = new Node(carry);
            tempNode.setNext(res);
            res = tempNode;
        }
        while(res!=null){
            System.out.print(res.getData());
            res=res.getNext();
        }
    }

    private static Node findSum(Node l1, Node l2, int diff){

        int length1 = findLength(l1);
        int length2 = findLength(l2);

        if(length1>length2){
            //l1 having more nodes
            Node res = findSum(l1.getNext(), l2, diff--);
            int data = l1.getData() + carry;
            if(data>9){
                carry=1;
                Node tempNode = new Node(data%10);
                tempNode.setNext(res);
                res = tempNode;
            }else{
                carry=0;
                Node tempNode = new Node(data);
                tempNode.setNext(res);
                res = tempNode;
            }
            return res;

        }else if(length2>length1){
            //l2 having more nodes
            Node res = findSum(l1, l2.getNext(), diff++);
            int data = l2.getData() + carry;
            if(data>9){
                carry=1;
                Node tempNode = new Node(data%10);
                tempNode.setNext(res);
                res = tempNode;
            }else{
                carry=0;
                Node tempNode = new Node(data);
                tempNode.setNext(res);
                res = tempNode;
            }
            return res;

        }else{
            //both have same length
            Node res = findSumForListOfSameSize(l1, l2);
            return res;
        }
    }

    private static Node findSumForListOfSameSize(Node l1, Node l2){
        if(l1==null && l2==null)
            return null;

        Node head = findSumForListOfSameSize(l1.getNext(), l2.getNext());

        int temp = l1.getData() + l2.getData() + carry;
        if(temp>9){
            carry=1;
        }else{
            carry=0;
        }

        if(head==null){
            head = new Node(temp % 10);
        }else{
            Node tempNode = new Node(temp % 10);
            tempNode.setNext(head);
            head = tempNode;
        }
        return head;
    }

    private static int findLength(Node node){
        int count=0;
        while(node!=null){
            count++;
            node = node.getNext();
        }
        return count;
    }
}

Answer 1

few notes on your implementation:

if(data>9){
            carry=1;
            Node tempNode = new Node(data%10);
            tempNode.setNext(res);
            res = tempNode;
        }else{
            carry=0;
            Node tempNode = new Node(data);
            tempNode.setNext(res);
            res = tempNode;
        }

can be rewritten as

 carry=data/10;
 Node tempNode = new Node(data%10);
 tempNode.setNext(res);
 res = tempNode;

• findSum(Node l1, Node l2, int diff)

  you call int length1 = findLength(l1);int length2 = findLength(l2); in every recursive call. It's enough to call it once, before you enter the recursion. The result won't change in the middle. it'll reduce the complexity of your solution from O(N^2) to O(n) All you need to do afterwards is decrement the value of diff until it becomes 0

I would rewrite the whole method as follows:

private static Node findSum(Node longer, Node shorter, int diff){
    if(diff==0){
         Node res = findSumForListOfSameSize(longer, shorter);
         return res;
    }
        Node res = findSum(longer.getNext(), shorter, diff--);
        int data = longer.getData() + carry;

        carry=data/10;
        Node tempNode = new Node(data%10);
        tempNode.setNext(res);
        res = tempNode;

        return res;
}

and the main would become

...
int length1 = findLength(l1);
int length2 = findLength(l2);
int diff = length1-length2;
if(diff<0){
    diff = diff * -1;
    Node res = findSum(templ21, templ11, diff);
}else{
    Node res = findSum(templ11, templ21, diff);
}
...

you could remove the need for static variable carry by doing this:

Node res = findSum(longer.getNext(), shorter, diff--);
int prevSum = res.getData()
int carry = prevSum / 1;
res.setData(prevSum % 10)

int sum = longer.getData() + carry;
Node tempNode = new Node(sum);

you're 'delegating' the calculation of the carry (and update of the vaue) to the next digit calculation). Also note, I renamed the data variable to be prevSum and sum

Answer 2

There is a neat fact about the Java LinkedList. It implements the Double Ended Queue or Deque interface. This means that it can be walked in either order (end backwards or start forwards) so in this case you actually don't need to find it's length, you just need to walk both lists backwards.

Here's an implementation of what you are trying to do.

/**
 * Add the two lists together as if they were numbers.
 *
 * @param la - List a
 * @param lb - List b
 * @return - The result list.
 */
private LinkedList<Integer> add(LinkedList<Integer> la, LinkedList<Integer> lb) {
    LinkedList<Integer> r = new LinkedList<>();
    // Walk backwards - because Java give you that for free.
    Iterator<Integer> ia = la.descendingIterator();
    Iterator<Integer> ib = lb.descendingIterator();
    // Keep track of a carry.
    Integer carry = 0;
    // Stop when both empty and carry is exhausted.
    while (ia.hasNext() || ib.hasNext() || carry != 0) {
        // Add them up.
        Integer sum = (ia.hasNext() ? ia.next() : 0) + (ib.hasNext() ? ib.next() : 0) + carry;
        // Extract the digit.
        Integer digit = sum % 10;
        // Work out the carry.
        carry = (sum - digit) / 10;
        // Add them up.
        r.addFirst(digit);
    }
    return r;
}

/**
 * Make an `int` into a List.
 *
 * @param n - the `int`
 * @return - the list equivalent.
 */
private LinkedList<Integer> asLinkedList(int n) {
    // Grow my list.
    LinkedList<Integer> l = new LinkedList<>();
    while (n > 0) {
        // Add the digits.
        l.addFirst(n % 10);
        // Div by 10.
        n /= 10;
    }
    if (l.size() == 0) {
        l.add(0);
    }
    return l;
}

/**
 * Make a `List` into an `int`
 *
 * @param l - the list.
 * @return - The lists value.
 */
private int asValue(LinkedList<Integer> l) {
    // Start at 0.
    int value = 0;
    // For each digit.
    for (Integer i : l) {
        // Mul by 10 and add the new digit.
        value = (value * 10) + i;
    }
    return value;
}

// Test the above.
private void test(int a, int b, int expected) {
    // Get my two lists.
    LinkedList<Integer> la = asLinkedList(a);
    LinkedList<Integer> lb = asLinkedList(b);
    System.out.println("a = " + la);
    System.out.println("b = " + lb);
    // Calculate the asum.
    LinkedList<Integer> rnsr = add(la, lb);
    System.out.print("rnsr = " + rnsr + " - ");
    // Extract value.
    int value = asValue(rnsr);
    // Check it.
    if (value == expected) {
        System.out.println("Passed");
    } else {
        System.out.println("FAILED! " + rnsr + " != " + expected);
    }
}

public void test() {
    test(542, 98799, 99341);
}

Note also the asLinkedList and asValue methods that avoid your manual creation of the lists.

Note also how I calculate the carry rather than explicitly set it to 0 or 1. It is calculated to be the value remaining after the digit has been extracted from the sum divided by 10.

Finally, see how using Iterators allows you to interrogate each list to see if it is exhausted and, if it is, use 0. This way we don't need to special case one being longer or shorter than the other.