Add Two Numbers
MediumDigit by digit with a running carry
Problem
Two non-negative numbers are stored as linked lists with the least-significant digit first. Add them and return the sum as a linked list.
Walk both lists together adding digits and a carry, exactly like grade-school addition.
The idea
The lists already store digits least-significant first, so a single simultaneous walk with a carry produces the answer directly. Treat a missing node as a zero and keep going until both lists and the carry are exhausted.
The trick
- Missing nodes contribute 0 — no need to pad the shorter list.
- The final carry becomes an extra node.
- O(max(m, n)) time.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — l1 = [2, 4, 3], l2 = [5, 6, 4] Values: 2, 4, 3.
1dummy = Node(); cur = dummy; carry = 02while a or b or carry:3 s = (a?a.val:0) + (b?b.val:0) + carry4 carry = s / 105 cur.next = Node(s % 10); cur = cur.next6 a = a?.next; b = b?.next7return dummy.nextInput
- array
- [2, 4, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = 2 -> 4 -> 3, b = 5 -> 6 -> 4
- Output:
- 7 -> 0 -> 8
- Explanation:
- 342 + 465 = 807 (stored reversed).
Example 2
- Input:
- a = 0, b = 0
- Output:
- 0
- Explanation:
- 0 + 0 = 0.
Example 3
- Input:
- a = 9 -> 9, b = 1
- Output:
- 0 -> 0 -> 1
- Explanation:
- 99 + 1 = 100.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.