Add Two Numbers

Medium#2dummy head

Two whole numbers, 0 or more, are given as linked lists of their digits, the ones digit first: 957 is 7 → 5 → 9. Return their sum as a list of the same kind. Our example: 7 → 5 → 9 (957) and 6 → 8 (86) — the answer is 3 → 4 → 0 → 1, that is 1043.

2 Add Two NumbersWalkthrough · 1×

Example: 7 → 5 → 9 (957) + 6 → 8 (86). Digits of one column stand one under the other; the answer grows on the bottom row.

l1l2nonenone75968dummyl1l2
digit not reached yetl1 and l2digit added to sumtailadded / in the answer

A dummy node: the digits of the answer will hang off it

01/43
restart · back · play · step
Speed
1function addTwoNumbers(l1, l2):
2 dummy = new node
3 tail = dummy
4 carry = 0
5 while l1 is not none or l2 is not none or carry > 0:
6 sum = carry
7 if l1 is not none:
8 sum = sum + l1.val
9 l1 = l1.next
10 if l2 is not none:
11 sum = sum + l2.val
12 l2 = l2.next
13 tail.next = new node(sum mod 10)
14 tail = tail.next
15 carry = floor(sum / 10)
16 return dummy.next
state
l1
7
l2
6
sum
–
carry
–
tail
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The lists start from the ones digit, so walking them adds column by column, like on paper: each column gives one digit, sum mod 10, and a carry, floor(sum / 10).
  2. A list that has run out adds 0, so numbers of different lengths need no special case.
  3. The loop also runs while carry is more than 0: after the last digits are added, the carry still becomes a new node, here the 1 of 1043.

Complexity

Time O(max(n, m)): one step per column. Memory O(max(n, m)) for the answer list, O(1) besides it.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.