8
\$\begingroup\$

Write code to sum two numbers represented by a linked list. The digits in this linked list are in reverse order. eg. (9->2->3) + (4->8->2) = (3->1->6)

Any comments on my solution (especially on the testing part)?

public class ListNode {
    private int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    ListNode(ListNode other){
        val = other.val;
    }

    boolean hasNext() {
        if (this.next != null) {
            return true;
        } else {
            return false;
        }
    }

    public int getVal(){
        return this.val;
    }

    public void setVal(int v){
        this.val = v;
    }
}
public class SumTwo {
    /**
     * Iterative
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbersV1(ListNode l1, ListNode l2) {
        if (l1 == null){
            l1 = new ListNode(0);
        }
        if (l2 == null){
            l2 = new ListNode(0);
        }

        int carry = 0;
        int total = l1.getVal() + l2.getVal() + carry;
        int num = total % 10;
        carry = total / 10;

        ListNode result = new ListNode(num);
        ListNode r = result;

        l1 = l1.next;
        l2 = l2.next;

        while (l1 != null || l2 != null) {
            if (l1 == null){
                l1 = new ListNode(0);
            }
            if (l2 == null){
                l2 = new ListNode(0);
            }

            total = l1.getVal() + l2.getVal() + carry;
            num = total % 10;
            carry = total / 10;

            r.next = new ListNode(num);
            r = r.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        // if carry != 0 then add it
        if (carry == 1){
            r.next = new ListNode(1);
        }

        return result;
    }
public class SumTwoUtils {
    public String printLinkedList(ListNode l){
        StringBuffer s = new StringBuffer();
        while (l != null){
            s.append(l.getVal());
            if (l.next != null){
                s.append("->");
            }
            l = l.next;
        }
        return s.toString();
    }
}
public class TestSumTwo {
    @Test
    public void testPrintLinkedList(){
        ListNode l = new ListNode(1);
        ListNode l2 = l;
        l2.next = new ListNode(2);
        l2 = l2.next;
        l2.next = new ListNode(3);
        String expected = "1->2->3";
        SumTwoUtils ut = new SumTwoUtils();
        String result = ut.printLinkedList(l);
        assertEquals(expected, result);
    }

    @Test
    public void testSameLinkedListNoCarry(){
        // Create list 1->2->3
        ListNode l = new ListNode(1);
        ListNode l2 = l;
        l2.next = new ListNode(2);
        l2 = l2.next;
        l2.next = new ListNode(3);

        // sum it to itself
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();

        ListNode n = sm.addTwoNumbersV1(l,l);

        String result = ut.printLinkedList(n);
        String expected = "2->4->6";

        assertEquals(expected, result);
    }

    @Test
    public void testSameSizeNoCarry(){
        // Create list 1->2->3
        ListNode l1 = new ListNode(1);
        ListNode ll1 = l1;
        ll1.next = new ListNode(2);
        ll1 = ll1.next;
        ll1.next = new ListNode(3);

        // Create list 4->6->2
        ListNode l2 = new ListNode(4);
        ListNode ll2 = l2;
        ll2.next = new ListNode(6);
        ll2 = l2.next;
        ll2.next = new ListNode(2);

        // sum them
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();
        ListNode n = sm.addTwoNumbersV1(l1,l2);

        // Expected result
        String expected = "5->8->5";

        // Result
        String result = ut.printLinkedList(n);

        assertEquals(expected, result);
    }

    @Test
    public void testSameSizeAndCarry(){
        // Create list 9->2->3
        ListNode l1 = new ListNode(9);
        ListNode ll1 = l1;
        ll1.next = new ListNode(2);
        ll1 = ll1.next;
        ll1.next = new ListNode(3);

        // Create list 4->8->2
        ListNode l2 = new ListNode(4);
        ListNode ll2 = l2;
        ll2.next = new ListNode(8);
        ll2 = l2.next;
        ll2.next = new ListNode(2);

        // sum them
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();
        ListNode n = sm.addTwoNumbersV1(l1,l2);

        // Expected result
        String expected = "3->1->6";

        // Result
        String result = ut.printLinkedList(n);

        assertEquals(expected, result);
    }

    @Test
    public void testSameSizeCarryEnd(){
        // Create list 1->2->8
        ListNode l1 = new ListNode(1);
        ListNode ll1 = l1;
        ll1.next = new ListNode(2);
        ll1 = ll1.next;
        ll1.next = new ListNode(8);

        // Create list 4->7->8
        ListNode l2 = new ListNode(4);
        ListNode ll2 = l2;
        ll2.next = new ListNode(7);
        ll2 = l2.next;
        ll2.next = new ListNode(8);

        // sum them
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();
        ListNode n = sm.addTwoNumbersV1(l1,l2);

        // Expected result
        String expected = "5->9->6->1";

        // Result
        String result = ut.printLinkedList(n);

        assertEquals(expected, result);
    }

    @Test
    public void testDifferentSizesNoCarry(){
        // Create list 2->8
        ListNode l1 = new ListNode(2);
        ListNode ll1 = l1;
        ll1.next = new ListNode(8);

        // Create list 4->1->8
        ListNode l2 = new ListNode(4);
        ListNode ll2 = l2;
        ll2.next = new ListNode(1);
        ll2 = l2.next;
        ll2.next = new ListNode(8);

        // sum them
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();
        ListNode n = sm.addTwoNumbersV1(l1,l2);

        // Expected result
        String expected = "6->9->8";

        // Result
        String result = ut.printLinkedList(n);

        assertEquals(expected, result);
    }

    @Test
    public void testDifferentSizesAndCarry(){
        // Create list 2->8
        ListNode l1 = new ListNode(2);
        ListNode ll1 = l1;
        ll1.next = new ListNode(8);

        // Create list 4->7->8
        ListNode l2 = new ListNode(4);
        ListNode ll2 = l2;
        ll2.next = new ListNode(7);
        ll2 = l2.next;
        ll2.next = new ListNode(8);

        // sum them
        SumTwo sm =  new SumTwo();
        SumTwoUtils ut = new SumTwoUtils();
        ListNode n = sm.addTwoNumbersV1(l1,l2);

        // Expected result
        String expected = "6->5->9";

        // Result
        String result = ut.printLinkedList(n);

        assertEquals(expected, result);
    }
\$\endgroup\$
  • \$\begingroup\$ Why are you not using java.util.LinkedList? \$\endgroup\$ – Emily L. May 18 '15 at 23:09
10
\$\begingroup\$

ListNode doesn't need to be mutable. You can remove the setter and set the value in the constructor. The result would be cleaner.

hasNext could return simply this.next != null; there is no need for the tedious if-else statement.

If one of the received ListNode is null, you can return the other node immediately. That will simplify quite a bit, and eliminate some duplicated logic you have going on there.

SumTwoUtils is a simple utility class with no data. You could make its only method static, and call it without an instance.

The tests... Are tedious and repetitive. You created a helper method to convert a linked list to string, but you could go further, and create a helper to do the reverse: linked list from integer. That would simplify the tests a lot, and make them a lot more readable too.

Suggested implementation

class ListNode {
    final int val;
    final ListNode next;

    public ListNode(int val) {
        this(val, null);
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return addTwoNumbers(l1, l2, false);
}

private ListNode addTwoNumbers(ListNode l1, ListNode l2, boolean carry) {
    if (l1 == null) {
        return withCarryApplied(l2, carry);
    }
    if (l2 == null) {
        return withCarryApplied(l1, carry);
    }

    int sum = l1.val + l2.val + (carry ? 1 : 0);
    boolean nextCarry = sum >= 10;
    int val = nextCarry ? sum - 10 : sum;

    return new ListNode(val, addTwoNumbers(l1.next, l2.next, nextCarry));
}

private ListNode withCarryApplied(ListNode node, boolean carry) {
    if (!carry) {
        return node;
    }
    return addTwoNumbers(new ListNode(1), node, false);
}

For testing:

private ListNode toListNode(int num) {
    if (num > 0) {
        return new ListNode(num % 10, toListNode(num / 10));
    }
    return new ListNode(0);
}

private int toInt(ListNode node) {
    if (node == null) {
        return 0;
    }
    if (node.next != null) {
        return node.val + 10 * toInt(node.next);
    }
    return node.val;
}

private int addTwoNumbersHelper(int n1, int n2) {
    ListNode l1 = toListNode(n1);
    ListNode l2 = toListNode(n2);
    return toInt(addTwoNumbers(l1, l2));
}

private void assertValid(int n1, int n2) {
    assertEquals(n1 + n2, addTwoNumbersHelper(n1, n2));
}

@Test
public void test_1_99() {
    assertValid(1, 99);
}

@Test
public void test_329_284() {
    assertValid(329, 284);
}
\$\endgroup\$
7
\$\begingroup\$

First thing that catches my eye.. Where are the comments?! I mean if you write good code, you don't have to write a lot of comments. But you literally have almost no useful comments in your code. What are you doing here?
ListNode result = new ListNode(num); ListNode r = result;

You never do anything to modify result, yet at the end of the method you return result? Some comments would go a good way in explaining that a bit.



You have this throughout your SumTwo class:

if (l1 == null){
    l1 = new ListNode(0);
}
if (l2 == null){
    l2 = new ListNode(0);
}

This can be placed into it's own method so that you don't have to repetitively type it throughout the code:':

public ListNode nullCheck (ListNode node) {
   if (node == null) {
      return new ListNode(0);
   }
   else {
      return node;
   }
}

This can be called as follows: l1 = nullCheck(l1);



You have this copy constructor in your ListNode class, which is confusing because your class is mutable. Typically, we only need a copy constructor if an object is immutable. If you wish to keep the copy constructor, remove the setter and getter and change the copy constructor to this:

ListNode(ListNode other){
    val  = other.val;
    next = other.next;
}

Otherwise, I would remove the copy constructor; it really has no purpose if your class is mutable. On the topic of mutability, you have one private member and one public member? It's a bit odd that you would expose the next node, but keep the values private. I would change the ListNode next; to be private: private ListNode next; and then I would create getters and setters for it. Only do this if you are required for some reason to have mutable Linked List.


Your hasnext() method can be simplified dramatically:

public boolean hasNext() {
   return this.next != null;
}

This is a simple boolean comparison, so you can literally just return the result of the comparison and not have to make a bulky if-statement.


I think that Janos did a good job touching on making your SumTwoUtils class a simple static method. I agree with him about your use of tests also. You put in a lot of code (more than your actual list and program) to do some really basic tests. I would honestly just keep it to one method.

\$\endgroup\$
  • 1
    \$\begingroup\$ "Typically, we only need a copy constructor if an object is immutable." - The other way round? \$\endgroup\$ – maaartinus May 19 '15 at 4:00

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.