Add Two Numbers II
Medium · Linked Lists · Linked List · Math · Stack
Problem
Two non-negative integers are stored in linked lists l1 and l2, one digit per node, with the most significant digit at the head.
Return their sum as a linked list, also most significant digit first. Neither input has leading zeros, except the number 0 itself.
Examples
Input: l1 = [6,5], l2 = [9,8,7] Output: [1,0,5,2]
65 + 987 = 1052. The carry out of the hundreds makes a new leading digit.
Input: l1 = [0], l2 = [0] Output: [0]
0 + 0 = 0.
Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]
7243 + 564 = 7807.
Constraints
- Each list has between 1 and 100 nodes
- 0 <= Node.val <= 9
- Neither list represents a number with leading zeros
Approaches
- Baseline: two stacks — time O(n + m), space O(n + m)
Follow-up
If you may not modify the input lists, use the stack version: it reads the lists without changing them, at O(n + m) extra space. With 100 digits the numbers do not fit any built-in integer type, so converting to a number only works in languages with big integers. The use cases subtract two such numbers and add three.
Related problems
Start free on Cariara · Coding problems · System design studio
