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;

}

for (int item : items) {
}
}
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
* @return              the node such that  its length to end is same as that of smaller linkedlist
*/
int index = 0;
Node node = first;

index++;
node = node.next;
}
return node;
}

/**
*
*
*/
if (ll.size == 0 || size == 0) {
throw new IllegalArgumentException("Either one of the linkedlist is empty this addition is not possible.");
}

Node longLLFirst = null;  // the first node of the longer linkedlist
Node smallLLFirst = null; // the first node of the smaller linkedlist
int difference = 0;

if (ll.size > size) {
longLLFirst = ll.first;
smallLLFirst = first;
difference =  ll.size - size;
} else {
longLLFirst = first;
smallLLFirst = ll.first;
difference = size - ll.size;
}

NodeCarryData ncd =  addTwoLL (longLLStart, smallLLFirst);
NodeCarryData ncd1 = addCarryToLL (longLLFirst, longLLStart, ncd);

if (ncd1.carry > 0) {
Node n = new Node(ncd1.carry);
n.next = ncd1.node;
} else {
}
}

/**
*
* @param node1     the start node of the longer linkedlist
* @param node2     the first node of the smaller linkedlist.
* @return          The NodeCarry data containing, new node, and the carry.
*/
private NodeCarryData addTwoLL (Node node1, Node node2) {
if (node1 == null)  { return new NodeCarryData(null, 0); }

int value = node1.item + node2.item + ncdReturn.carry;

Node newNode = new Node(value % 10);
newNode.next = ncdReturn.node;

return new NodeCarryData(newNode, value / 10);
}

/**
* Adds the carry to the remaning portion of the longer linkedlist
*
* @param node      the start node of longer linkedist
* @param n         the node of longer linkedlist upto which we should consider the limit to start adding carry
* @param ncd       the node carry data obtained by adding equal lengths of linkedlist.
* @return          the node carry data
*/
private NodeCarryData addCarryToLL (Node node, Node n, NodeCarryData ncd) {
if (node == n) return new NodeCarryData(ncd.node, ncd.carry);

NodeCarryData ncdReturn = addCarryToLL(node.next, n, ncd);
int value  = node.item + ncdReturn.carry;

Node newNode = new Node(value % 10);
newNode.next = ncdReturn.node;

return new NodeCarryData(newNode, value / 10);
}

// size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
public List<Integer> toList() {
List<Integer> list = new ArrayList<>();
if (first == null) return list;

for (Node x = first; x != null; x = x.next) {
}

return list;
}

@Override
public int hashCode() {
int hashCode = 1;
for (Node x = first; x != null; x = x.next)
hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
return hashCode;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node currentListNode = first;
Node otherListNode =  other.first;

while (currentListNode != null && otherListNode != null) {
if (currentListNode.item != otherListNode.item) return false;
currentListNode = currentListNode.next;
otherListNode = otherListNode.next;
}
return currentListNode == null && otherListNode == null;
}
}

@Test
public void testUnEqual() {
// testing unequal length.
assertEquals(expected1, result1);
}

@Test
public void testEqual() {
// testing equal length.
assertEquals(expected2, result2);
}

@Test
public void testUnEqualBC() {
// testing carry + unequal legnth of array
assertEquals(expected3, result3);
}

@Test
public void testEqualBC() {
// testing carry + equal length of array
assertEquals(expected4, result4);
}

}

• This looks way too overengineered to me. The way I have it in mind is that you can get it done with a traditional linkedlist with the addition of a method int getNumberRepresentation(). All that's needed aside from that is splitting the number into separate numbers and add it to a linkedlist where needed. I'm at work so I have no time to write some code for it myself, but perhaps you can clarify the difference between that approach and yours? Commented Jul 18, 2014 at 7:02
• Thats not allowed since it simplifies the bar for interview. Commented Jul 19, 2014 at 19:26

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;
for (int d : digits) {
Node n = new Node(d);
if (prev == null) {
} else {
prev.next = n;
}
prev = n;
}
}

// 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);

• Your main() produces incorrect output. Commented Jul 31, 2014 at 22:49
• @rolfl, there is an error in your recursive function in line carry = nxt.digit - 9; - this leads to very big carry. It should be carry = 1 instead. Commented Jan 1, 2015 at 17:40