Linked List · 067Medium
Add Two Numbers
You are given two non-empty linked lists representing non-negative integers whose digits are stored in REVERSE order, one digit per node. Add them and return the sum as a linked list in the same reverse-order form.
Constraints
- Each list holds 1 to 100 nodes.
- 0 <= Node.val <= 9
- No leading zeros except the number 0 itself.
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
addTwoNumbers(2 -> 4 -> 3, 5 -> 6 -> 4) -> 7 -> 0 -> 8 // 342 + 465 = 807 addTwoNumbers(0, 0) -> 0 addTwoNumbers(9 -> 9, 1) -> 0 -> 0 -> 1 // 99 + 1 = 100 addTwoNumbers(5, 5) -> 0 -> 1 // 5 + 5 = 10, carry makes a new node addTwoNumbers(1 -> 2 -> 3, 7) -> 8 -> 2 -> 3 // 321 + 7 = 328 addTwoNumbers(0, 7 -> 3) -> 7 -> 3 // 0 + 37 = 37, different lengths
Edge cases
- Lists of different lengths.
- A final carry needs an extra node (99 + 1).
- Digits are already reversed, so add left to right.
Show the target complexity (spoiler)
- Naive
- Converting each list to a number, adding, and rebuilding overflows for 100-digit
- Target
- O(max(m, n)) time — walk both lists together, tracking a carry and emitting sum % 10 each step.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/06-linked-list/067-add-two-numbers.js ./practice c 067