#2
Add Two Numbers
Medium Digit-by-digit with carry
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Two non-negative numbers are stored as linked lists with digits in reverse order (ones digit first). Return their sum as a list in the same format.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add two numbers stored backwards as lists of digits.
Why this works: the ones digit comes first, so add digit by digit with a carry, just like on paper.
Example: 2→4→3 (342) + 5→6→4 (465)
2+5 = 7, 4+6 = 10 → 0 carry 1, 3+4+1 = 87 → 0 → 8 (807)
✦Hints open one at a time
Add like on paper, starting from the ones digit — which is already the head.
Keep going while either list has nodes or there's a carry left.
↗Approach
Dummy head and a carry. Each step: sum = carry + digits available; append sum % 10; carry = sum / 10.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) { sum += l1.val; l1 = l1.next; }
if (l2 != null) { sum += l2.val; l2 = l2.next; }
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
}
return dummy.next;
}
}!Common mistake
Stopping when both lists end and forgetting a final carry (e.g. 5 + 5 = 10 needs a new node).
Complexity
- Time: O(max(n, m)).
- Space: O(max(n, m)) for the output.
Topic: Linked List
🎬 Episodes 40–45: video coming soon