java - Calculating the Sum of values in a linked list

Question

I got a programming question at an interview recently.

There are 2 linked lists. Each node stores a value from 1 through 9 (indicating one index of the number). Hence 123 would be a linked list 1->2->3

The task was to create a function:

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

that would return the sum of the values in the 2 linked list arguements.

If the array a is: 1->2->3->4

And the array b is: 5->6->7->8

The answer should be: 6->9->1->2

Here is my algorithm:

Go through each node in a and b, get the values as an integer and add them. Create a new linked list with the those values.

Here is the code: It runs with a complexity of O(n) roughly I assume. Once through each of the array inputs and once to create the output array.

Any improvements? Better algorithms... or code improvements

public class LinkedListNode {
        LinkedListNode next;
        int value;

    public LinkedListNode(int value) {
        this.value = value;
        this.next = null;
    }

    static int getValue(LinkedListNode node) {
        int value = node.value;
        while (node.next != null) {
            node = node.next;
            value = value * 10 + node.value;
        }
        return value;
    }

    static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
        LinkedListNode answer = new LinkedListNode(0);
        LinkedListNode ans = answer;
        int aval = getValue(a);
        int bval = getValue(b);
        int result = aval + bval;
        while (result > 0) {
            int len = (int) Math.pow((double) 10,
                    (double) String.valueOf(result).length() - 1);
            int val = result / len;
            ans.next = new LinkedListNode(val);
            ans = ans.next;
            result = result - val*len;
            }    
        return answer.next;
    }
}

Answer 1

Other solutions I have seen for this problem involve building the returned list incrementally by iterating backwards over both the input lists at the same time adding each element as you go to a new list. That way is more complicated because you have to add each element and deal with carry overs.

If the array a is: 1->2->3->4

And the array b is: 5->6->7->8

Iterate backwards

Then 4 + 8 = 12 (returned list current = 2)

carry the 1

(1) + 3 + 7 = 11 (returned list = 1-> 2)

carry the 1

(1) + 2 + 6 = 9 (returned list = 9 -> 1 ->2 )

1 + 5 = 6 ( return list = 6->9>1->2)

You can implement this by using Stacks to get the LIFO nature to iterate backwards if the list is only singly linked.