LeetCode 2 · Linked List

Add Two Numbers, explained with a picture

Two odometer trains, digit by digit.

MediumLinked List
▶ Watch it step by step

The problem

Two non-negative numbers are stored as linked lists with digits in reverse order (ones digit first). Add them and return the sum as a list in the same format.

Input:  2 → 4 → 3  (342)  and  5 → 6 → 4  (465)
Output: 7 → 0 → 8  (807)

Picture it

Picture two trains where each coach is one digit, ones digit at the front, like an odometer read backwards. Just like adding on paper, we add the two front digits plus any carry, write the last digit of that sum on a new coach, and carry the tens to the next column. If a carry is left at the end, it becomes one more coach.

How to recognise it

  • Two numbers arrive as digit lists, and the digits are stored ones digit first. That is exactly the order in which you add numbers on paper, right to left.
  • The numbers can be longer than any built-in integer type (LeetCode allows 100 digits), so converting to an integer is not safe in most languages.
  • The answer is a new list in the same format, so you build it one node per column, using a dummy node to avoid a special case for the first digit.
  • Anything that says "add digit by digit with a carry" (big-number strings, binary strings) is the same column addition.

Start with brute force

Turn each list into an integer, add the integers, and turn the sum back into a list.

def add_brute(l1, l2):
    def to_int(node):
        num, place = 0, 1
        while node:
            num += node.val * place
            place *= 10
            node = node.next
        return num
    total = to_int(l1) + to_int(l2)
    dummy = tail = Node(0)
    while True:
        total, digit = divmod(total, 10)
        tail.next = Node(digit)
        tail = tail.next
        if total == 0:
            return dummy.next

In Python this works and is fast enough for 100 digits, because Python integers have no size limit. In Java or C++ a 64-bit integer holds only about 19 digits, so a 100-digit number overflows. The problem is designed so you add the digits yourself.

From brute force to the idea

  1. Find the waste. Converting builds a huge number only to break it apart again. The lists already give you the digits in the order you need them.
  2. Add one column at a time. Walk both lists together. For each column, s = carry + digit from l1 + digit from l2, using 0 for a list that has already ended.
  3. Split the column sum. divmod(s, 10) gives the new carry (0 or 1) and the digit to write. The largest column sum is 9 + 9 + 1 = 19, so the carry never exceeds 1.
  4. Append to the result. A dummy node means every digit is added the same way: tail.next = Node(digit), then move tail.
  5. Keep going while anything is left. The loop runs while l1 or l2 or carry. The carry part adds a final 1 when the last column overflows, as in 5 + 5 = 10.

This is the key idea: school column addition, walking both lists at once and carrying into the next node.

The key idea

Column addition walking both lists at once, carrying as you go. O(max(m, n)).

Python solution

def add(l1, l2):            # digits stored backwards
    dummy = tail = Node(0)
    carry = 0
    while l1 or l2 or carry:
        s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
        carry, digit = divmod(s, 10)
        tail.next = Node(digit)
        tail = tail.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

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.

Complexity

ApproachTimeSpace
Brute forceO(m + n) loop steps, but each big-integer operation grows with the number, so up to O((m + n)²) digit workO(max(m, n)) for the result, plus the big integers
Column addition (shown code)O(max(m, n)): one loop step per column, plus at most one for the final carryO(max(m, n)) for the result list; O(1) besides it

Edge cases

  • Different lengths (9 → 9 → 9 → 9 plus 9 → 9, 9,999 + 99): missing digits count as 0, giving 8 → 9 → 0 → 0 → 1 (10,098).
  • Final carry (5 plus 5): the loop runs once more for the carry and returns 0 → 1.
  • Both zero (0 plus 0): returns a single 0 node, not an empty list.
  • Carry through a long run (9 → 9 → 9 plus 1): returns 0 → 0 → 0 → 1.
  • The inputs are not changed: the shown code only reads them and creates new nodes.

Common mistakes

  • Looping while l1 and l2, which stops at the end of the shorter number and drops the rest.
  • Leaving or carry out of the loop condition, so 5 + 5 returns 0 instead of 0 → 1.
  • Setting carry = 1 when s >= 10 but never back to 0 when s < 10. The carry is then added to every later column, and with or carry in the condition the loop never ends.
  • Reading l1.val without checking that l1 exists, which raises AttributeError once the shorter list ends.
Your turn: digits stored forwards

The same task, but each list stores its digits most significant first: 7 → 2 → 4 → 3 (7,243) plus 5 → 6 → 4 (564) gives 7 → 8 → 0 → 7 (7,807). Do not reverse the input lists. Describe your approach, then write it if you like.

Compare with our answer

Addition must still start at the ones digit, which is now at the end. Push each list's digits onto a stack, then pop from both: the stacks give the digits right to left. Each new digit belongs in front of the ones already written, so build the result by prepending.

def add_forward(l1, l2):
    s1, s2 = [], []
    while l1:
        s1.append(l1.val)
        l1 = l1.next
    while l2:
        s2.append(l2.val)
        l2 = l2.next
    head, carry = None, 0
    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)       # prepend: we work right to left
    return head

Time O(m + n), space O(m + n) for the stacks.

A strong answer mentions: why the ones digit must come first, stacks (or reversing) to get that order, prepending new digits, and the final carry.

Check what stuck

1. Two non-negative numbers of up to 10^5 digits arrive as strings, in a language without big integers. Which approach fits best?

2. Why does the shown code run in O(max(m, n)) time rather than O(m · n)?

3. A learner changes the loop to while l1 or l2:. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.