Add two numbers represented by linked lists
Add Two Numbers Represented by Linked Lists
Problem Statement
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
Example
Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807
Input: l1 = [0], l2 = [0]
Output: [0]
Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output: [8, 9, 9, 9, 0, 0, 0, 1]
Explanation: 9999999 + 9999 = 10009998
Brute Force Approach (Convert to Numbers)
Intuition
Convert both linked lists to numbers, add them, and convert the result back to a linked list. However, this can overflow for very large numbers.
Algorithm
- Convert first list to number (traversing and building)
- Convert second list to number
- Add the two numbers
- Create a new linked list from the sum
Implementation
Complexity Analysis
- Time Complexity: O(max(m, n)) - Traverse both lists
- Space Complexity: O(max(m, n)) - Result list
Note: This approach has overflow issues for very large numbers.
Optimal Approach (Digit by Digit Addition)
Intuition
Since both lists are already in reverse order (least significant digit first), we can directly add corresponding digits from both lists while maintaining a carry. This mimics how we add numbers by hand.
Algorithm
- Initialize carry = 0
- Traverse both lists simultaneously
- For each position:
- sum = l1.val + l2.val + carry
- digit = sum % 10
- carry = sum / 10
- Create new node with digit
- Handle remaining nodes in longer list
- Handle final carry if exists
Visualization
l1: 2 -> 4 -> 3 (342)
l2: 5 -> 6 -> 4 (465)
↓ ↓ ↓
Position 0: 2 + 5 + 0 = 7, digit = 7, carry = 0
Position 1: 4 + 6 + 0 = 10, digit = 0, carry = 1
Position 2: 3 + 4 + 1 = 8, digit = 8, carry = 0
Result: 7 -> 0 -> 8 (807)
Implementation
Complexity Analysis
- Time Complexity: O(max(m, n)) - Traverse both lists once
- Space Complexity: O(max(m, n)) - Result list (O(1) if we don't count output)
Variant: Numbers Stored in Forward Order
If digits are stored in forward order (most significant digit first):
Input: l1 = [3, 4, 2], l2 = [4, 6, 5]
(342 + 465)
Output: [8, 0, 7] (807)
Approach
- Reverse both lists
- Add as in the optimal approach
- Reverse the result
Or use stacks to process from the end:
Variant: Different Length Lists (Without Padding)
The optimal solution already handles different length lists naturally by checking if each list has remaining nodes.
Key Takeaways
- Reverse order storage makes addition straightforward (LSD first)
- The dummy node technique simplifies head handling
- Always handle the final carry - don't forget it!
- The condition
l1 || l2 || carryelegantly handles all cases - For forward order storage, use stacks or reverse the lists
- This problem is a classic interview question (LeetCode #2)
- The digit-by-digit approach avoids overflow issues