## 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.


b'
\n

## Solution

\n

Intuition

\n

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.

\n \n

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

\n

Algorithm

\n

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 .

\n

The pseudocode is as following:

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

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.

\n

Take extra caution of the following cases:

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Test caseExplanation
\n
\n
When one list is longer than the other.
\n
\n
When one list is null, which means an empty list.
\n
\n
The sum could have an extra carry of one at the end, which is easy to forget.
\n\n

Complexity Analysis

\n
\n
• \n

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

\n
• \n
• \n

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

\n
• \n
\n

Follow up

\n

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

\n

\n\n

\n
'