Add Two Numbers

Q: What is the time complexity of adding two numbers stored as linked lists?

It is O(max(L1, L2)) : one step per column, plus one more when a carry is left at the end. Apart from the answer, the single-pass version uses O(1) memory: two pointers and the carry.

MediumLinked list Math and simulation

+10

You get two non-negative whole numbers, each stored as a singly linked list of its digits with the least significant digit first. In the first list, node i holds the digit values1[i] and links to node next1[i]. The second list works the same way with next2 and values2. In both lists -1 ends the list and the head is node 0. The nodes are not stored in list order, so follow the links.

Return the digits of the sum of the two numbers, least significant digit first.

Function

addTwoNumbers(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: the index of the node each node of the first number links to, or -1 for its last node
values1integer-array: the digit held by each node of the first number
next2integer-array: the index of the node each node of the second number links to, or -1 for its last node
values2integer-array: the digit held by each node of the second number
Returnsinteger-array: the digits of the sum, least significant first

Constraints

1 ≤ L1 ≤ 100, where L1 is the length of next1 and of values1.
1 ≤ L2 ≤ 100, where L2 is the length of next2 and of values2.
0 ≤ values1[i], values2[j] ≤ 9
Each entry of next1 is -1 or a node index of the first list, and each entry of next2 is -1 or a node index of the second list.
Starting at node 0, each list visits every one of its nodes exactly once and then reaches -1. There is no cycle.
No number has leading zeros: the last node of a list holds a digit other than 0, unless the list is the single digit 0.

Examples

Input: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
Output: [5, 4, 1, 1]
Explanation: The first list visits nodes 0, 2, 1 and reads 8, 1, 6, the number 618. The second reads 7, 2, 5, the number 527. Their sum is 1145, so the answer is 5, 4, 1, 1.

Input: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
Output: [0, 0, 0, 0, 1]
Explanation: The second list reads 1, 9, 9, 9, the number 9991. Adding 9 gives 10000: every column produces a 0 and a carry, and the last carry becomes a fifth digit.

Input: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
Output: [7, 5]
Explanation: The first number is 0 and the second list reads 7, 5, the number 57. Adding 0 changes nothing, so the answer is [7, 5].

Follow-up

How would you add the numbers if the lists stored the most significant digit first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The numbers are too long for any integer type, so add them as on paper: column by column, carrying a 1 when a column reaches 10. The lists store the ones digit first, so walking them visits the columns in the order you add them.

Copy the digits out, then add column by column

Intuition

A pointer here is a node index, and moving forward is node = next[node]. Copy each list's digits into an array, so index i holds the digit worth 10^i: [8, 1, 6] and [7, 2, 5] in the first example.

Then add as on paper, counting a missing digit as 0. Each column writes sum % 10 and carries the rest: 8 + 7 = 15 writes 5 and carries 1, 1 + 2 + 1 = 4, and 6 + 5 = 11 writes 1. The last carry becomes a final digit: [5, 4, 1, 1].

The copies cost O(L1 + L2) extra memory that the addition never needs.

Algorithm

Walk each list from node 0 and copy its digits into an array.
Set carry = 0. For each index i up to the longer array's length, add the digits at i that exist and the carry.
Append sum % 10 and set carry to sum / 10, rounded down.
If the carry is 1 after the last column, append it.

def readDigits(next, values):
    # The digits in list order: least significant first.
    digits = []
    node = 0
    while node != -1:
        digits.append(values[node])
        node = next[node]
    return digits


def addTwoNumbers(next1, values1, next2, values2):
    first = readDigits(next1, values1)
    second = readDigits(next2, values2)
    result = []
    carry = 0
    for i in range(max(len(first), len(second))):
        column = carry
        if i < len(first):
            column += first[i]
        if i < len(second):
            column += second[i]
        result.append(column % 10)
        carry = column // 10
    if carry > 0:
        result.append(carry)
    return result

Walk both lists at once with a carry

Intuition

Column i uses only the i-th node of each list, so keep one pointer per list, a and b, and move both as the columns go by.

One loop runs while a is not -1, or b is not -1, or the carry is 1. A pointer that still has a node adds its digit and steps forward; a pointer at -1 adds nothing. That handles numbers of different lengths without a second loop, and the carry condition writes the extra digit at the end.

On the second example, 9 plus 9991, every column sums to 10 and writes 0. After four columns both lists are done, but the carry is 1, so the loop runs once more: [0, 0, 0, 0, 1]. Apart from the answer, it keeps three integers.

Algorithm

Set a = 0, b = 0 and carry = 0.
While a != -1 or b != -1 or carry > 0, start the column sum at carry.
If a != -1, add values1[a] and set a = next1[a]. Do the same for b with the second list.
Append sum % 10 and set carry to sum / 10, rounded down.
Return the digits you appended.

def addTwoNumbers(next1, values1, next2, values2):
    a = 0  # current node of the first number
    b = 0  # current node of the second number
    carry = 0
    result = []
    # Keep going while either number has digits left or a carry is waiting.
    while a != -1 or b != -1 or carry > 0:
        column = carry
        if a != -1:
            column += values1[a]
            a = next1[a]
        if b != -1:
            column += values2[b]
            b = next2[b]
        result.append(column % 10)  # the digit this column writes
        carry = column // 10  # 1 when the column reached 10, else 0
    return result

Pitfalls and edge cases

Converting each list to an integer and adding. A 100 digit number overflows every 64-bit type.
Dropping the final carry. A loop that stops when both lists end returns [0, 0, 0, 0] for the second example.
Stopping when the shorter list ends. The second example then loses the three 9s of 9991 and the carry running through them.
Reading the digits in array order. In the first example values1 is [8, 6, 1], but the number is 618, read along the links.
Forgetting the offset in Lua and R, where arrays start at 1. Keep node ids 0-based and read next1[node + 1].

Frequently asked questions3

Why are the digits stored in reverse order in Add Two Numbers?

Addition starts at the ones digit, and a singly linked list can only be walked from its head. With the least significant digit first, the walk visits the columns in the order you add them, so the carry moves forward with the pointers.

What is the time complexity of adding two numbers stored as linked lists?

It is O(max(L1, L2)): one step per column, plus one more when a carry is left at the end. Apart from the answer, the single-pass version uses O(1) memory: two pointers and the carry.

Can the carry ever be larger than 1?

No. A column adds two digits of at most 9 and a carry of at most 1, so its sum is at most 19. Dividing by 10 and rounding down gives 0 or 1.

def addTwoNumbers(next1, values1, next2, values2):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next1 = [2, -1, 1]
values1 = [8, 6, 1]
next2 = [2, -1, 1]
values2 = [7, 5, 2]

Expected Output

[5, 4, 1, 1]