3
\$\begingroup\$

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<Integer> 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 index = 0;
        Node node = first;

        while (index < advance) {
            index++;
            node = node.next;
        } 
        return node;
    }


    /**
     * Adds the two linkedlists.
     * This addition is from right to left, like mathematical addition.
     * 
     * 
     * @param ll    the linkedlist to add to the current one.
     * @return      a newly added linkedlist.
     */
    public SumLinkedListRev sumLL(SumLinkedListRev ll) {
        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;
        }

        Node longLLStart = advanceFirstNode(longLLFirst, difference); 
        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;
            return new SumLinkedListRev(n); 
        } else { 
            return new SumLinkedListRev(ncd1.node); 
        }
    }  


    /**
     * Adds two linkedlist of equal length.
     * 
     * @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); }

        NodeCarryData ncdReturn = addTwoLL(node1.next, node2.next);
        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) {
            list.add(x.item);
        }

        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;
        SumLinkedListRev other = (SumLinkedListRev) obj;
        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;
    }
}

public class SumLinkedListRevTest {

    @Test
    public void testUnEqual() {
        // testing unequal length.
        SumLinkedListRev ll1 = new SumLinkedListRev(Arrays.asList(1, 2, 3, 4, 5));
        SumLinkedListRev ll2 = new SumLinkedListRev(Arrays.asList(1, 2, 3, 4));
        SumLinkedListRev result1 = ll1.sumLL(ll2);
        SumLinkedListRev expected1 = new SumLinkedListRev(Arrays.asList(1, 3, 5, 7, 9));
        assertEquals(expected1, result1);
    }

    @Test
    public void testEqual() {
        // testing equal length.
        SumLinkedListRev ll3 = new SumLinkedListRev(Arrays.asList(1, 2, 3, 4, 5));
        SumLinkedListRev ll4 = new SumLinkedListRev(Arrays.asList(1, 2, 3, 4, 5));
        SumLinkedListRev result2 = ll3.sumLL(ll4);
        SumLinkedListRev expected2 = new SumLinkedListRev(Arrays.asList(2, 4, 6, 9, 0));
        assertEquals(expected2, result2);
    }

    @Test
    public void testUnEqualBC() {
        // testing carry + unequal legnth of array
        SumLinkedListRev ll5 = new SumLinkedListRev(Arrays.asList(9, 9, 9, 9));
        SumLinkedListRev ll6 = new SumLinkedListRev(Arrays.asList(2, 3, 4));
        SumLinkedListRev result3 = ll5.sumLL(ll6);
        SumLinkedListRev expected3 = new SumLinkedListRev(Arrays.asList(1, 0, 2, 3, 3));
        assertEquals(expected3, result3);
    }

    @Test
    public void testEqualBC() {
        // testing carry + equal length of array
        SumLinkedListRev ll7 = new SumLinkedListRev(Arrays.asList(9, 9, 9, 9));
        SumLinkedListRev ll8 = new SumLinkedListRev(Arrays.asList(1, 2, 3, 4));
        SumLinkedListRev result4 = ll7.sumLL(ll8);
        SumLinkedListRev expected4 = new SumLinkedListRev(Arrays.asList(1, 1, 2, 3, 3));
        assertEquals(expected4, result4);
    }

}
\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$ – Jeroen Vannevel Jul 18 '14 at 7:02
  • \$\begingroup\$ Thats not allowed since it simplifies the bar for interview. \$\endgroup\$ – JavaDeveloper Jul 19 '14 at 19:26
6
\$\begingroup\$

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);
}
\$\endgroup\$
8
  • \$\begingroup\$ "There is a way to solve it, using recursion" Did you check the GeeksForGeeks link? They provide a recursion solution with C++ there. \$\endgroup\$ – Simon Forsberg Jul 31 '14 at 21:44
  • \$\begingroup\$ Your main() produces incorrect output. \$\endgroup\$ – 200_success Jul 31 '14 at 22:49
  • \$\begingroup\$ @SimonAndréForsberg - nope, if there's not enough info in the description, then the question is poor, so, I tend to not follow links to descriptions, and if more infor is needed, I comment. \$\endgroup\$ – rolfl Jul 31 '14 at 22:59
  • \$\begingroup\$ @rolfl I just think it was a nice coincidence that you suggested a solution that was provided in the original (GeeksForGeeks) description :) I haven't compared your version with that though. \$\endgroup\$ – Simon Forsberg Jul 31 '14 at 23:26
  • \$\begingroup\$ @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. \$\endgroup\$ – HitOdessit Jan 1 '15 at 17:40

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.