3
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This is a pointless exercise. Either the numbers are small and then there's no problem to create a better data structure (i.e., convert to int, long, or BigInteger and simply add). Or they're big and you get a StackOverflowError. One could argue with \$O(1)\$ memory, but then the stack must be counted as well. \$\endgroup\$ – maaartinus May 31 '15 at 22:37
  • \$\begingroup\$ @maaartinus why would there be an overflow if you store the sum as a linked list as well? \$\endgroup\$ – Daniel Sokolov May 31 '15 at 23:56
  • \$\begingroup\$ @DanielSokolov You get the stack overflow when traversing the list recursively. Every recursive call needs an own stack frame and the stack is usually pretty limited as each thread needs its own (and you may want hundreds of threads). \$\endgroup\$ – maaartinus Jun 1 '15 at 0:02
  • \$\begingroup\$ @maaartinus, I agree, hint to use recursion is quite puzzling. Especially, given the fact that proposed solution does create a 3-rd list. Same result can be easily achieved by iterative aproach \$\endgroup\$ – Daniel Sokolov Jun 1 '15 at 0:30
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice... I never thought the way you wrote Liked it. \$\endgroup\$ – Jayesh Jun 1 '15 at 4:21
  • \$\begingroup\$ Just one question, is it possible to get solution without using static variable which i took for "carry" variable? \$\endgroup\$ – Jayesh Jun 1 '15 at 4:23
  • \$\begingroup\$ @Jayesh The static variable makes it non thread-safe. You could create an instance for the computation and use its variable. You could pass a "mutable int", e.g., new int[1] around to be filled. You could return an instance of class NodeAndCarry`. There's no call by reference nor similar things in Java. Here, I'd go for the instance creation. \$\endgroup\$ – maaartinus Jun 1 '15 at 7:25
  • \$\begingroup\$ @Jayesh, I'm glad you find it useful. I edited my answer with a suggestion of how to get rid of the static carry var \$\endgroup\$ – Daniel Sokolov Jun 1 '15 at 10:56
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.