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.ExampleInput:First List: 5->6->3  // represents number 563   Second List: 8->4->2 //  represents number 842OutputResultant list: 1->4->0->5  // represents number 1405public 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);    }}
Add two numbers represented by a linked list
java;algorithm;linked list