Add Two Numbers

Средняя№2фиктивная голова

Два целых неотрицательных числа даны связными списками своих цифр, начиная с единиц: 957 — это 7 → 5 → 9. Нужно вернуть их сумму таким же списком. Наш пример: 7 → 5 → 9 (957) и 6 → 8 (86) — ответ 3 → 4 → 0 → 1, то есть 1043.

2 Add Two NumbersРазбор · 1×

Пример: 7 → 5 → 9 (957) + 6 → 8 (86). Цифры одного разряда стоят друг под другом; ответ растёт в нижней строке.

l1l2nonenone75968dummyl1l2
цифра, до которой не дошлиl1 и l2цифра, которую прибавляемtailсложена / в ответе

Фиктивный узел: на нём будут висеть цифры ответа

01/43
сначала · назад · пуск · шаг
Скорость
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
состояние
l1
7
l2
6
sum
–
carry
–
tail
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Списки начинаются с единиц, поэтому проход складывает разряд за разрядом, как в столбик: каждый разряд даёт цифру, sum mod 10, и перенос, floor(sum / 10).
  2. Кончившийся список добавляет 0, поэтому числа разной длины не требуют отдельного случая.
  3. Цикл идёт и пока carry больше 0: когда последние цифры сложены, перенос всё равно становится новым узлом, здесь это 1 из 1043.

Сложность

Время O(max(n, m)): по шагу на разряд. Память O(max(n, m)) на список-ответ, кроме него O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.