Сложение списков

Описание задачи

Сложить два больших неотрицательных числа, представленных связными списками. Цифры идут в обратном порядке (LSD first).

Формат

A: 2 -> 3 -> 9  (Число 932)
B: 5 -> 3 -> 1  (Число 135)
Result: 7 -> 6 -> 0 -> 1 (Число 1067)

Исходные списки менять нельзя. Результат — новый список.

Алгоритм

• Идём по обоим спискам одновременно.
• sum = A->val + B->val + carry
• newNode->val = sum % 10
• carry = sum / 10
• Если один список кончился — продолжаем только со вторым + carry.
• Если оба кончились, но carry > 0 — добавляем узел с carry.