Add two numbers represented by a linked list

This question is attributed to GeeksForGeeks:


Given two numbers represented by two linked lists, write a function
that returns sum list. The sum list is linked list representation of
addition of two input numbers. It is not allowed to modify the lists.
Also, not allowed to use explicit extra space.


Example


Input:


First List: 5->6->3 // represents number 563

Second List: 8->4->2 // represents number 842


Output


Resultant list: 1->4->0->5 // represents number 1405

```
public class SumLinkedListRev {

private Node first;
private Node last; // this dude remains uninitialized
private int size;

public SumLinkedListRev() {
}

public SumLinkedListRev(List items) {
for (int item : items) {
add(item);
}
}
private SumLinkedListRev(Node first) {
this.first = first;
}

public void add (int item) {
Node node = new Node(item);
if (first == null) {
first = last = node;
} else {
last.next = node;
last = last.next;
}
size++;
}

private static class Node {
private Node next;
private int item;

Node(int item) {
this.item = item;
}
}

private static class NodeCarryData {
private Node node;
private int carry;

NodeCarryData(Node node, int carry) {
this.node = node;
this.carry = carry;
}
}

/**
* Traverse the longer linkedlist, to a node, such that from
* that node onwards, its length to end is same as that of smaller linkedlist
*
*
* @param first the first node of longer linkedlist
* @param advance the length to advance from the first node
* @return the node such that its length to end is same as that of smaller linkedlist
*/
private Node advanceFirstNode(Node first, int advance) {
int i

This is failing on the 'do not use any additional space' test. You are creating new objects (non-node) which have the value and the carry options.

In effect, the only new memory you can allocate off the stack, are a single node for each digit in the sum, which will be the same, or one larger, than the number of digits in the largest input list.

Your solution involves a whole class of data that is not returned (NodeCarryData).

As a result, your code does not solve the problem within the constraints of the specification.

There is a way to solve it, using recursion. The trick is to first identify the length of each input, and to then find a way to align the recursion so that you descend each input so that you reach their least significant digits at the same time.

Then, when you exit the recursion, you do the sum values on the upward traversal of the recursion stack. In a sense, this is easier to explain with code, rather than text:

private static final class Node {
    private int digit;
    private Node next;

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

    @Override
    public String toString() {
        // recursive to-string, easy, not too fast though
        return digit + (next == null ? "" : next.toString());
    }

}

// convert an input array to a Node linked list.
private static final Node convert(int...digits) {
    Node prev = null;
    Node head = null;
    for (int d : digits) {
        Node n = new Node(d);
        if (prev == null) {
            head = n;
        } else {
            prev.next = n;
        }
        prev = n;
    }
    return head;
}

// add two lists given with no off-stack memory other than the result.
public static final Node add(final Node a, final Node b) {
    final int as = size(a);
    final int bs = size(b);

    Node n = nodeAdd(as - bs, a, bs - as, b);
    if (n.digit > 9) {
        // there is a carry overflow. Insert a new node.
        Node x = new Node(1);
        x.next = n;
        n.digit -= 10;
        return x;
    }
    return n;
}

// get the number of digits in the input.
private static final int size(Node n) {
    int s = 0;
    while (n != null) {
        s++;
        n = n.next;
    }
    return s;
}

// recursive method.
private static final Node nodeAdd(final int askip, final Node a, final int bskip, final Node b) {

    if(a == null || b == null) {
        return null;
    }

    // if askip is positive, we need to skip a-nodes in the recursion.
    // if bskip is positive, we need to skip b-nodes.
    // this is how we align the two lists to have the same least-significant-digit.
    // note, we decrement askip and bskip at each level.
    Node nxt = nodeAdd(askip - 1, bskip > 0 ? a : a.next, bskip - 1, askip > 0 ? b : b.next);

    int carry = 0;
    if (nxt != null && nxt.digit > 9) {
        carry = nxt.digit / 10;
        nxt.digit %= 10;
    }
    carry += askip <= 0 ? b.digit : 0;
    carry += bskip <= 0 ? a.digit : 0;
    Node ret = new Node(carry);
    ret.next = nxt;
    return ret;
}

public static void main(String[] args) {
    Node a = convert(1,2,3,4,5);
    Node b = convert(2,3,4,5);
    Node s = add(a,b);
    System.out.println(s);
}

StackExchange Code Review Q#57350, answer score: 6