Forward Digit List Sum

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 most significant to the least significant, the way the number is written on paper. For instance, 503 is stored as 5 → 0 → 3. Return their sum as a list in the same format, most significant digit first. Both lists are non-empty and have no leading zeros, except the number 0 itself, which is a single node. Try to do it without reversing the input lists.

Example 1

first=list_node([3, 0, 8]), second=list_node([9, 5]) → [4, 0, 3]

The lists encode 308 and 95; 308 + 95 = 403.

Example 2

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

999 + 2 = 1001: the carry ripples through every digit and the result gains a new leading digit.

Example 3

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

0 + 61 = 61.

Constraints

Each list has 1 to 100 nodes
0 ≤ Node.val ≤ 9
The first node is not 0 if the list has more than one node

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Linked List Math

Similar problems

Double the Digit Chain Medium Adding Digit Lists Medium Tree Into a Right Chain Medium List Folded From Both Ends Medium Postfix Calculator Medium

Input

first=list_node([3, 0, 8]), second=list_node([9, 5])

Expected

[4, 0, 3]

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