Adding Digit Lists

Medium

Two non-negative integers are stored in the singly linked lists first and second. Each node holds one digit, and the digits go from the least significant to the most significant. For instance, 503 is stored as 3 → 0 → 5. Return their sum as a list in the same format, least significant digit first. Both lists are non-empty. The numbers have no leading zeros, except for the number 0 itself, which is a single node.

Example 1

first=list_node([5, 1]), second=list_node([7, 9]) → [2, 1, 1]

The lists encode 15 and 97; 15 + 97 = 112, which reversed is [2, 1, 1].

Example 2

first=list_node([0]), second=list_node([4, 3, 2]) → [4, 3, 2]

0 + 234 = 234.

Example 3

first=list_node([9, 9]), second=list_node([1]) → [0, 0, 1]

99 + 1 = 100: the carry ripples through every digit and adds a new one.

Constraints

Each list has between 1 and 100 nodes
0 ≤ Node.val ≤ 9
The last node (the most significant digit) is not 0 unless the list has a single node

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Linked List Math

Similar problems

Trade Places in Twos Medium Fast Exponentiation Medium List Folded From Both Ends Medium Every Bracketing Result Medium Add One to a Digit Chain Medium

Input

first=list_node([5, 1]), second=list_node([7, 9])

Expected

[2, 1, 1]

Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.