Add Two Numbers
Problem
Given two non-empty linked lists representing two non-negative integers in reverse order, return a linked list representing their sum in the same reverse order format, where each node contains a single digit. You may assume the two numbers do not contain any leading zeros, except the number 0 itself.
- The number of nodes in each linked list is in the range [1, 100]
- 0 ≤ Node.val ≤ 9
- It is guaranteed that the list represents a number that does not have leading zeros
Example
l1 = [2,4,3], l2 = [5,6,4][7,0,8]The numbers represented are 342 and 465. Adding them yields 807. The output linked list represents 708 in reverse order. The algorithm iterates through both lists simultaneously, adding corresponding digits and carrying over any overflow. At index 0, 2 + 5 = 7 with no carry. At index 1, 4 + 6 = 10, so 0 is stored and carry 1 is forwarded. At index 2, 3 + 4 + 1 (carry) = 8, stored as is. The final linked list is [7,0,8].
Approach
Straightforward Solution
Convert both linked lists to integers, sum them, and then convert back to a linked list. This approach is inefficient and can cause integer overflow for very large numbers.
Core Observation
Adding two numbers digit-by-digit from least significant to most significant is analogous to traversing two linked lists simultaneously, summing node values and carrying over any overflow to the next digit.
Path to Optimal
The key insight is to simulate the addition process as done by hand: iterate through both linked lists simultaneously, sum the digits along with any carry, create a new node for the digit part of the sum, and carry over the remainder. This avoids integer conversion and handles arbitrarily large numbers.
Optimal Approach
Use a dummy head node to simplify list construction. Initialize carry to zero. Loop while either list has nodes or carry is non-zero. At each iteration, extract values from current nodes or zero if none, sum with carry, update carry, create a new node with the digit, and advance pointers. Return the next node of dummy head as the result.
Time
O(max(m, n))
The algorithm traverses both linked lists once, where m and n are their lengths. Each node is processed exactly once.
Space
O(max(m, n))
The output linked list can be at most one node longer than the longer input list due to carry. The auxiliary space is O(1) excluding the output list.
Pattern Spotlight
Linked List (Digit-by-Digit Simulation)
When adding numbers represented as linked lists in reverse order, simulate elementary addition by traversing both lists simultaneously, summing digits and carry, and building the result list on the fly without converting to integers.
Solution
| 1 | class Solution:
|
| 2 | def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
|
| 3 | dummy = ListNode()
|
| 4 | curr = dummy
|
| 5 | carry = 0
|
| 6 |
|
| 7 | while l1 or l2 or carry:
|
| 8 | v1 = l1.val if l1 else 0
|
| 9 | v2 = l2.val if l2 else 0
|
| 10 |
|
| 11 | val = v1 + v2 + carry
|
| 12 | carry = val // 10
|
| 13 | val = val % 10
|
| 14 | curr.next = ListNode(val)
|
| 15 |
|
| 16 | curr = curr.next
|
| 17 | l1 = l1.next if l1 else None
|
| 18 | l2 = l2.next if l2 else None
|
| 19 |
|
| 20 | return dummy.next |
| 1 | class Solution { |
| 2 | public ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
| 3 | ListNode dummy = new ListNode(); |
| 4 | ListNode curr = dummy; |
| 5 | int carry = 0; |
| 6 | |
| 7 | while (l1 != null || l2 != null || carry != 0) { |
| 8 | int v1 = l1 != null ? l1.val : 0; |
| 9 | int v2 = l2 != null ? l2.val : 0; |
| 10 | |
| 11 | int val = v1 + v2 + carry; |
| 12 | carry = val / 10; |
| 13 | val = val % 10; |
| 14 | curr.next = new ListNode(val); |
| 15 | |
| 16 | curr = curr.next; |
| 17 | l1 = l1 != null ? l1.next : null; |
| 18 | l2 = l2 != null ? l2.next : null; |
| 19 | } |
| 20 | |
| 21 | return dummy.next; |
| 22 | } |
| 23 | } |
Step-by-Step Solution
Initialize Dummy Head, Current Pointer, and Carry
| 3 | dummy = ListNode()
|
| 4 | curr = dummy
|
| 5 | carry = 0
|
Objective
To set up the initial state for building the result linked list and tracking carry during addition.
Key Insight
Using a dummy head node simplifies edge cases by providing a fixed starting point for the result list, avoiding special handling for the first node. Initializing carry to zero prepares for the addition process, ensuring correct propagation of overflow digits.
Interview Quick-Check
Core Logic
The dummy node acts as a sentinel to simplify list construction, allowing uniform insertion of new nodes.
State & Boundaries
Carry must be initialized to zero to correctly accumulate overflow from digit sums.
Traverse Both Lists and Accumulate Sum with Carry
| 7 | while l1 or l2 or carry:
|
| 8 | v1 = l1.val if l1 else 0
|
| 9 | v2 = l2.val if l2 else 0
|
| 11 | val = v1 + v2 + carry
|
| 12 | carry = val // 10
|
| 13 | val = val % 10
|
| 14 | curr.next = ListNode(val)
|
| 16 | curr = curr.next
|
| 17 | l1 = l1.next if l1 else None
|
| 18 | l2 = l2.next if l2 else None
|
Objective
To iterate through both input lists simultaneously, summing corresponding digits and carry, and appending the result digit to the output list.
Key Insight
At each iteration, the algorithm extracts the current digit from each list or zero if the list is exhausted, sums these with the carry, and computes the new digit and carry. This simulates manual addition digit-by-digit. The loop condition ensures all digits and any remaining carry are processed, guaranteeing correctness even when lists differ in length or a final carry remains.
Interview Quick-Check
Core Logic
The loop continues while either list has nodes or there is a carry, ensuring all digits and overflow are processed.
State & Boundaries
Extracting digit values with conditional expressions handles lists of unequal length gracefully.
Common Pitfalls & Bugs
Forgetting to advance pointers or update carry correctly can cause infinite loops or incorrect sums.
Complexity
Each node is processed once, resulting in O(max(m, n)) time complexity.
Return the Result Linked List Skipping Dummy Head
| 20 | return dummy.next |
Objective
To return the head of the newly constructed linked list representing the sum.
Key Insight
The dummy head node was a placeholder to simplify list construction. Returning dummy.next skips this placeholder and returns the actual start of the result list.
Interview Quick-Check
Core Logic
Returning dummy.next returns the constructed sum list without the dummy placeholder.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
while l1 or l2 or carry:Continue looping while there are nodes in l1 or l2 or a non-zero carry.
This loop condition guarantees processing all digits and any leftover carry, handling lists of unequal length and final overflow.
carry = val // 10Update carry by dividing sum by 10 (integer division).
Carry is the overflow digit to be added in the next iteration, ensuring correct multi-digit addition.
dummy = ListNode()Create a dummy head node to anchor the result linked list.
The dummy node simplifies list construction by providing a fixed starting point, eliminating the need for special cases when adding the first node.
carry = 0Initialize carry to zero for digit addition overflow.
Carry tracks overflow from summing digits, ensuring correct addition across multiple nodes.
val = v1 + v2 + carryCalculate the sum of digits and carry.
This sum represents the total for the current digit position before splitting into digit and carry.
val = val % 10Update val to the remainder of sum modulo 10.
This extracts the single digit to store in the current node, representing the current place value.
curr.next = ListNode(val)Create a new node with the computed digit and append it to the result list.
Appending the new digit node builds the output linked list representing the sum.
return dummy.nextReturn the next node after dummy, which is the head of the result list.
Skipping the dummy node returns the actual sum list, completing the construction.
curr = dummyInitialize a pointer to track the current node in the result list.
This pointer advances as new nodes are appended, enabling sequential construction of the result list.
v1 = l1.val if l1 else 0Extract the current digit from l1 or zero if l1 is exhausted.
Using zero for exhausted lists ensures addition logic remains uniform without special cases.
v2 = l2.val if l2 else 0Extract the current digit from l2 or zero if l2 is exhausted.
Symmetric to l1 extraction, this maintains consistent addition logic for both lists.
curr = curr.nextAdvance the current pointer to the newly added node.
Moving the pointer forward prepares for appending the next digit node.
l1 = l1.next if l1 else NoneAdvance l1 pointer if not None.
Moving to the next digit in l1 ensures all digits are processed sequentially.
l2 = l2.next if l2 else NoneAdvance l2 pointer if not None.
Moving to the next digit in l2 ensures all digits are processed sequentially.
Test Your Understanding
Why must the loop continue while there is a carry even if both input lists are exhausted?
Because the carry represents an overflow digit from the last addition, which must be included as a new node to correctly represent the sum.
Related Problems
Linked Lists pattern
Don't just read it. Drill it.
Reconstruct Add Two Numbers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Add Two Numbers drill