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

• Emily L.: Why are you not using java.util.LinkedList?

Answer 1

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

Answer 2

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.

• maaartinus: "Typically, we only need a copy constructor if an object is immutable." - The other way round?