Add two numbers in Linked List
MediumWalk both, carrying as you go
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
With least-significant digits first, walk both lists together summing the digits plus the carry and appending each result digit. Continue while either list has nodes or a carry remains, which handles unequal lengths without a separate pass.
The trick
- Loop while `a || b || carry` — the carry alone can require one more node.
- digit = sum % 10, carry = sum / 10.
- A dummy head keeps the append loop free of special cases.
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.