linked-list
math
simulation
You are given two non-empty linked lists, l1 and l2, representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list, in the same reversed-digit form.
You may assume neither number has a leading zero, except the number 0 itself.
Input / output
- Input:
l1: ListNode,l2: ListNode(JSON test fixtures are plain arrays of digits, least-significant digit first, e.g.[2, 4, 3]means the number 342) - Output:
ListNode— the sum, digits in the same reversed order (serialized the same way)
Constraints
- The number of nodes in each list is between 1 and 100.
0 <= node value <= 9- Neither number has a leading zero, unless the number itself is 0.
Follow-up
Can you do this in a single pass with O(1) extra space beyond the output list, without ever converting either list to an integer (which would fail for arbitrarily large numbers)?
Examples
Example 1
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Example 2 (both zero)
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3 (carry cascades through the longer list)
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.