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 {
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
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();
assertEquals(expected, result);
}

@Test
// 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();

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

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

// Result

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

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

// Result

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

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

// Result

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

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

// Result

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

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

// Result

assertEquals(expected, result);
}

• Why are you not using java.util.LinkedList? May 18 '15 at 23:09

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

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


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

private void assertValid(int n1, int n2) {
}

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

@Test
public void test_329_284() {
assertValid(329, 284);
}


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? May 19 '15 at 4:00