LeetCode 445 · Linked list

Add Two Numbers II, explained with a picture

Adding from the back with two plate stacks.

Linked list
▶ Watch it step by step

The problem

Add two numbers stored as linked lists with the most significant digit first.

Input:  7 → 2 → 4 → 3 (7243) and 5 → 6 → 4 (564)
Output: 7 → 8 → 0 → 7 (7807)

Picture it

Picture each train’s digits stacked on plates: the ones digit ends up on top. Pop one plate from each stack, add with the carry, and put the result coach at the front of the answer train.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two stacks reverse the order for column addition; build the answer by prepending. O(m + n).

Python solution

def add(l1, l2):               # digits in normal order
    s1, s2 = values(l1), values(l2)   # two stacks
    carry, head = 0, None
    while s1 or s2 or carry:
        s = carry + (s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)
        carry, digit = divmod(s, 10)
        head = Node(digit, head)       # add to the front
    return head

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.