Linked list arithmetic

Question

I am practicing for interviews and I tried solving the problem on my own and got a solution. I was wondering how can I improve the performance and memory on this program?

The problem performs addition on linked list nodes. The nodes are 1s->10s->100s->.... The goal of this program is to perform addition on two of these linked lists. The output should be a linked list of the same format.

Example:

 1 -> 4 -> 3 
+ 1 -> 5 -> 9 -> 2 

Linked list output:

2 -> 9 -> 2 -> 3

Here is my code:

public class prob2_5 {
 /*
 * You have two numbers represented by a linked list, where each node contains a single digit.
 * The digits are stored in reverse order, such that the 1's digit is at the head of the list.
 * Write a function that adds the two numbers and returns the sum as a linked list
 * 
 */
 public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
 int l1sum = 0;
 int l2sum = 0;
 int multiplier = 1;
 while(l1 != null) {
 l1sum = l1sum + l1.value*multiplier;
 multiplier = multiplier*10;
 l1 = l1.next;
 }
 multiplier = 1;
 while(l2 != null) {
 l2sum = l2sum + l2.value*multiplier;
 multiplier = multiplier*10;
 l2 = l2.next;
 }
 int total = l2sum + l1sum;
 char[] totalnum = (total + "").toCharArray();
 int len = totalnum.length;
 LinkedListNode tail = new LinkedListNode(totalnum[len - 1] - '0');
 LinkedListNode newNode;
 LinkedListNode prevNode = tail;
 System.out.print(totalnum);
 for (int i = len - 2; i >= 0; i--) { 
 newNode = new LinkedListNode(totalnum[i] - '0');
 prevNode.next = newNode; 
 prevNode = newNode; 
 }
 return tail;
 } 
}

Here is my linked list class:

public class LinkedListNode {
 LinkedListNode next;
 int value;
 public LinkedListNode(int value) {
 this.next = null;
 this.value = value;
 }
}

• Simon Forsberg: What is your LinkedListNode implementation? Could you provide a runnable example? I didn't really understand your explanation completely.
• Liondancer: Sorry Ill add more to my post
• Simon Forsberg: OK, now I understand. 143 really represents the number 341, and 1592 is 2951. 2951 +たす 341 =わ 3292, which is 2923 backwards.
• Liondancer: yes exactly! =D

Answer 1

I believe you are missing the point of the exercise - instead of 'decoding' the input numbers, and then 're-encoding' the output number - you are supposed to iteratively get to the answer by going over the nodes of both lists:

public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
 return addLists(0, l1, l2);
}
private static LinkedListNode addLists(int carryOver, LinkedListNode l1, LinkedListNode l2) {
 // stop conditions
 if (l1 == null && l2 == null && carryOver == 0) {
 return null;
 }
 if (l1 == null) {
 l1 = new LinkedListNode(0);
 }
 if (l2 == null) {
 l2 = new LinkedListNode(0);
 }
 // iteration
 int addedValue = l1.value + l2.value + carryOver;
 carryOver = 0;
 if (addedValue >= 10) {
 addedValue -= 10;
 carryOver = 1;
 }
 l3 = new LinkedListNode(addedValue);
 // recursion
 l3.next = addLists(carryOver, l1.next, l2.next);
 return l3;
}

• 200_success: Instead of l1 = new LinkedListNode(0), I'd suggest creating a null object: private static final NULL_NODE = new LinkedListNode(0);

Answer 2

Uri has a good answer, this answer is just to add a second spin on the problem....

Recursion is a good tool to have, but it is not necessarily the best tool for all occasions. In this instance, it's a toss-up.... but the iterative solution to this problem is perhaps a simpler thing to read..... and should be considered. Additionally, in many cases an iterative solution will outperform a recursive solution. In this case, again, it is a toss-up because the lists will be so short.... but, if the list was long, the recursive approach will fail with a stack-overflow... the iterative approach will keep trucking though.

public static final LinkedListNode add(LinkedListNode a, LinkedListNode b) {
 // this pointer points to the result, it is not the actual result.
 final LinkedListNode pointer = new LinkedListNode(0);
 int carry = 0;
 LinkedListNode cursor = pointer;
 while (a != null || b != null) {
 int digitsum = carry;
 if (a != null) {
 digitsum += a.value;
 a = a.next;
 }
 if (b != null) {
 digitsum += b.value;
 b = b.next;
 }
 cursor.next = new LinkedListNode(digitsum % 10);
 carry = digitsum / 10;
 cursor = cursor.next;
 }
 if (carry != 0) {
 cursor.next = new LinkedListNode(carry);
 }
 // don't return the dummy pointer, return the actual result
 return pointer.next;
}

Some side-notes:

• the variables l1 and l2 are not great names....
• The LinkedListNode should probably have a final value, and there should be getters for the value and next, and a setter for the next.