Solution


Approach 1: Elementary Math

Intuition

Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.

Illustration of Adding two numbers

Figure 1. Visualization of the addition of two numbers: .
Each node contains a single digit and the digits are stored in reverse order.

Algorithm

Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of and . Since each digit is in the range of , summing two digits may "overflow". For example . In this case, we set the current digit to and bring over the to the next iteration. must be either or because the largest possible sum of two digits (including the carry) is .

The pseudocode is as following:

  • Initialize current node to dummy head of the returning list.
  • Initialize carry to .
  • Initialize and to head of and respectively.
  • Loop through lists and until you reach both ends.
    • Set to node 's value. If has reached the end of , set to .
    • Set to node 's value. If has reached the end of , set to .
    • Set .
    • Update .
    • Create a new node with the digit value of and set it to current node's next, then advance current node to next.
    • Advance both and .
  • Check if , if so append a new node with digit to the returning list.
  • Return dummy head's next node.

Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head's value.

Take extra caution of the following cases:

Test case Explanation

When one list is longer than the other.

When one list is null, which means an empty list.

The sum could have an extra carry of one at the end, which is easy to forget.

Complexity Analysis

  • Time complexity : . Assume that and represents the length of and respectively, the algorithm above iterates at most times.

  • Space complexity : . The length of the new list is at most .

Follow up

What if the the digits in the linked list are stored in non-reversed order? For example: