The 'Add two numbers' problem is a common problem you will find on various coding challenge sites such as LeetCode. This problem is an excellent introduction to working with Linked Lists and requires working with two Linked Lists to create a third List. To solve this type of problem, it is helpful to think about how you would solve it on paper before diving into the code.

The problem statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zeros, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

Approach

The problem states that the digits are stored in reverse order. This made me pause for a minute; however, it actually made solving this problem easier. If we write on paper a problem to add two numbers, we add them in reverse order.

// To add these numbers we would start from the
// right side (in reverse order)
 342
+465
----
 807

Thinking about how you would really add two numbers together can help us come up with an algorithm to solve this. It's just a matter of iterating through both lists and adding each number up (simulating starting on the right). There's a good chance we'll have to check for null if one number has more digits. And, we will also have to handle a carryover if two numbers have a sum greater than 9. See the comments in the code below for more details.

The Code

/**
 * Definition for singly-linked list.
 */
 public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
/**
 * Solution
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Head of the new Linked List - this will be the result
        ListNode result = new ListNode();
        // Reference of the result, which is empty at this point
        ListNode pointer = result;
        // Carry over number
        int carry = 0;

        while(l1 != null || l2 != null) {
            // if either value is null, use zero else use value
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            // do the adding
            int sum = x + y + carry;
            // calculate the carryover. Remember this is
            // integer division and will only return whole 
            // numbers. 
            carry = sum / 10;
            // At this point we add the total sum mod 10 to
            // the new node in the results list. If the
            // integer is greater than 10 this will return
            // the remainder. If its less than 10, it will
            // return the integer.
            pointer.next = new ListNode(sum % 10);
            pointer = pointer.next;

            // Move to next node
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // After the last iteration, check to see if there is
        // a carryover left, if so, add it to the results
        // list
        if (carry != 0) {
            pointer.next = new ListNode(carry);
        }

        return result.next;
    }
}

Complexity

Now we can figure out the complexity of our solution.

Time complexity

If the length of l1 is m and the length of l2 is n, then the solution above will be iterated up to m or n times. This gives a time complexity of O(max(m, n)).

Space complexity

O(max(m, n)), since we are creating a new linked list to return.

Final Thoughts

You can come up with an algorithm to handle a problem like this by thinking about how you would really add two numbers together. In some cases, coming up with an initial solution can be achieved by thinking about how you would address a problem in "real life" rather than using a programming language. This is one of the reasons why code challenge specialists recommend solving the problem using paper and sudo code before getting into the actual code. This technique helps you think about the problem itself and not the implementation. The solution presented above is just one way to solve this problem. Can you solve it more effectively or concisely? Comments below are welcome with additional solutions.

Header Photo by Andrew Neel