Add Forward Digit Chains

MediumLinked List

Problem

An invoicing system stores amounts as linked lists of decimal digits, most significant digit first: 7243 is [7, 2, 4, 3].

Given two such lists a and b (no leading zeros except the number 0 itself), return their sum in the same format. Do not reverse the input lists.

Example 1

Input:
a = [7, 2, 4, 3], b = [5, 6, 4]
Output:
[7, 8, 0, 7]

7243 + 564 = 7807.

Example 2

Input:
a = [9, 9], b = [1]
Output:
[1, 0, 0]

Constraints

  • 1 ≤ nodes in each list ≤ 1000
  • 0 ≤ node.val ≤ 9
  • No leading zeros, except the number 0 itself.

Hint

Show the first hint

Column addition must start at the ones digit, which is now at the tail. How can you visit digits from the end without reversing?

Walkthrough

How to approach it

01Clarify before coding

  • Which end is the most significant digit? The head.
  • May I reverse the inputs? No, they must stay untouched.
  • Can the lengths differ? Yes, and the result may gain a digit from the carry.

02Brute force

Read both lists into integers, add, and write the digits back.

Cost: O(n + m), but 1000-digit numbers overflow any fixed-width integer, so it is not language-independent.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.