LeetCode #2 Medium

Add Two Numbers

Two non-empty lists store digits in reverse order, one digit per node. Add the numbers and return the sum as a list, also in reverse order.

linked-listmathrecursion

Open on LeetCode ↗

02

Intuition

💡

Reverse order is a gift: the heads are the ones digits, so you can add left to right exactly like grade-school addition, carrying into the next node as you go.

03

Approach

1

Converting to integers doesn't scale

It's tempting to read each list into a number, add them, and rebuild — but the lists can be hundreds of digits long, far past what a native integer holds, and rebuilding throws away the very alignment the problem hands us. Better to add the lists directly, digit by digit.

2

Reverse storage means add left to right

The digits are stored in reverse order, so the heads are the ones place. That's a gift: it lets us add exactly the way we do by hand, starting from the least significant digit. Walk both lists in lockstep; at each position the column total is a + b + carry, the new digit is total % 10, and the carry into the next column is total // 10.

3

One loop, driven by lists-or-carry

Use a dummy head and append one result node per column. Loop while either list still has nodes or a carry remains — that last condition is what creates the extra leading digit in cases like 5 + 5 = 10. Treat a missing node as 0 so lists of different lengths just contribute zeros once exhausted. O(max(m,n)) time and space.

04

Solution & live demo

python

▶1class Solution:
▶2    def addTwoNumbers(self, l1, l2):
▶3        dummy = tail = ListNode(0)
▶4        carry = 0
▶5        while l1 or l2 or carry:
▶6            a = l1.val if l1 else 0
▶7            b = l2.val if l2 else 0
▶8            carry, digit = divmod(a + b + carry, 10)
▶9            tail.next = ListNode(digit)
▶10            tail = tail.next
▶11            l1 = l1.next if l1 else None
▶12            l2 = l2.next if l2 else None
▶13        return dummy.next

05

Edge cases

Different lengths, e.g. [9,9] + [1]

Treat a missing node as 0, so the shorter list simply contributes zeros once exhausted.

Final carry, e.g. [5] + [5] = [0,1]

The loop condition includes carry, so a trailing carry creates the extra high-order node.

Both single zeros

0 + 0 = 0 with no carry; one result node holding 0 is produced.

06

Complexity

Time

O(max(m, n))

Space

O(max(m, n))

One pass over the longer list; the result has at most one extra node.