Sum two linked lists

Question

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

\$\begingroup\$ Why are you not using java.util.LinkedList? \$\endgroup\$

Emily L.
– Emily L.

2015-05-18 23:09:09 +00:00
Commented May 18, 2015 at 23:09 — Emily L.
– Emily L., Commented May 18, 2015 at 23:09

janos · Accepted Answer · 2015-05-19 07:51:09Z

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

Evan Bechtol · Accepted Answer · 2015-05-19 00:55:46Z

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.

"Typically, we only need a copy constructor if an object is immutable." - The other way round? — maaartinus
– maaartinus, Commented May 19, 2015 at 4:00

Stack Exchange Network

Sum two linked lists

2 Answers 2

Suggested implementation

You must log in to answer this question.

Hot Network Questions

Sum two linked lists

2 Answers 2

Suggested implementation

You must log in to answer this question.

Related

Hot Network Questions