Add Two Numbers
MediumGiven two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.
Examples
Example 1: Basic Addition
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807. Starting from the ones place: 2+5=7, 4+6=10 (write 0, carry 1), 3+4+1=8.
Example 2: Zero Values
Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0. Edge case handled naturally by our algorithm.
Example 3: Different Length Lists
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: 9,999,999 + 9,999 = 10,009,998. The algorithm handles different lengths by using 0 when a list is exhausted.
Example 4: Final Carry
Input: l1 = [9,9], l2 = [1]
Output: [0,0,1]
Explanation: 99 + 1 = 100. The final carry creates an additional node in the result.
Explanation
To add two numbers represented as linked lists, we simulate the grade-school addition algorithm. We traverse both lists simultaneously, digit by digit, starting from the least significant digit (the head of each list, since digits are stored in reverse order).
At each step, we:
1. Add the current digits from both lists (if available)
2. Add any carry from the previous step
3. Create a new node with the sum's digit (sum % 10)
4. Update the carry for the next step (sum / 10)
5. Move to the next nodes in both lists
We continue until both lists are exhausted AND there's no carry left. The result is built in reverse order, which is perfect since the output should also be in reverse order!
The Dummy Node Pattern
One of the most elegant techniques in linked list problems is the dummy node. Instead of worrying about which node is the "head" of our result, we create a placeholder node at the start. This dummy node serves as an anchor, allowing us to build our result list without special cases.
At the end, we simply return dummy.next — the real result. Without a dummy node, you'd need conditional logic to handle the first node differently.
Edge Cases to Handle
- • Different length lists: Use the pattern
val if node else 0to handle exhausted lists gracefully - • Final carry: The loop condition must include
or carryto handle cases like 9+9=18 - • Single node lists: Both lists have only one digit
- • Zero values: Adding 0 + 0
Complexity Analysis
Time Complexity: O(max(m, n))
We iterate through the longer of the two lists. Each node is visited exactly once, making this a single-pass algorithm — optimal for this problem.
Space Complexity: O(max(m, n))
The result list can be at most one node longer than the longer input list (due to potential final carry). We create new nodes for the result.
Common Mistakes to Avoid
- • Forgetting the final carry: Not including
or carryin the loop condition - • Not handling different lengths: Assuming both lists have the same number of nodes
- • Creating unnecessary nodes: Creating a node for zero when there's no digit and no carry
- • Integer overflow: In languages with fixed-size integers, be mindful of large sums
Idea Map
Initialize dummy = new ListNode(0), carry = 0
Loop while l1 != null or l2 != null or carry > 0
1. sum = (l1?.val or 0) + (l2?.val or 0) + carry
2. carry = sum / 10
3. current.next = new ListNode(sum % 10)
4. current = current.next
5. Move l1 and l2 forward
Return dummy.next
Code
class ListNode:
Defines the ListNode class representing each node in the linked list with a value and a pointer to the next node.
def __init__(self, val=0, next=None):
Constructor that initializes a node with a value and optionally a reference to the next node.
def addTwoNumbers(l1, l2):
Main function that takes two linked list heads and returns their sum as a linked list.
dummy = ListNode(0)
Creates a dummy node to serve as the starting point. This simplifies edge cases where we need to create the first node.
current = dummy
`current` keeps track of the last node in our result list as we build it.
carry = 0
`carry` stores the overflow (0 or 1) when the sum of digits exceeds 9.
while l1 or l2 or carry:
Continue looping as long as there are digits to process in either list OR there's a carry remaining.
val1 = l1.val if l1 else 0
Get the value from l1's current node, or 0 if l1 is exhausted (null).
val2 = l2.val if l2 else 0
Get the value from l2's current node, or 0 if l2 is exhausted (null).
total = val1 + val2 + carry
Calculate the total sum of both digits plus any carry from the previous step.
carry = total // 10
Calculate new carry: 1 if total >= 10, otherwise 0.
current.next = ListNode(total % 10)
Create a new node with the ones digit of the total (0-9) and attach it to our result.
current = current.next
Move the current pointer forward to the newly created node.
if l1: l1 = l1.next
Move to the next node in l1 if there is one.
if l2: l2 = l2.next
Move to the next node in l2 if there is one.
return dummy.next
Return the actual result (skip the dummy node which was just a placeholder).
class ListNode {
Defines the ListNode class representing each node in the linked list.
int val;
The integer value stored in this node.
ListNode next;
Reference to the next node in the list.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Main function that takes two linked list heads and returns their sum as a linked list.
ListNode dummy = new ListNode(0);
Creates a dummy node to serve as the starting point, simplifying edge cases.
ListNode current = dummy;
`current` tracks the last node in our result list as we build it.
int carry = 0;
`carry` stores the overflow (0 or 1) when sum exceeds 9.
while (l1 != null || l2 != null || carry != 0) {
Continue while there are digits to process OR there's a remaining carry.
int val1 = (l1 != null) ? l1.val : 0;
Get the value from l1's current node, or 0 if l1 is exhausted.
int val2 = (l2 != null) ? l2.val : 0;
Get the value from l2's current node, or 0 if l2 is exhausted.
int sum = val1 + val2 + carry;
Calculate the total sum of both digits plus any carry.
carry = sum / 10;
Calculate new carry: 1 if sum >= 10, otherwise 0.
current.next = new ListNode(sum % 10);
Create a new node with the ones digit and attach it to our result.
current = current.next;
Move the current pointer forward to the newly created node.
if (l1 != null) l1 = l1.next;
Move to the next node in l1 if there is one.
if (l2 != null) l2 = l2.next;
Move to the next node in l2 if there is one.
}
End of while loop.
return dummy.next;
Return the actual result (skip the dummy node which was just a placeholder).
}
End of the function.
struct ListNode {
Defines the ListNode structure representing each node in the linked list.
int val;
The integer value stored in this node.
ListNode *next;
Pointer to the next node in the list.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
Main function that takes two linked list heads and returns their sum as a linked list.
ListNode* dummy = new ListNode(0);
Creates a dummy node to serve as the starting point, simplifying edge cases.
ListNode* current = dummy;
`current` tracks the last node in our result list as we build it.
int carry = 0;
`carry` stores the overflow (0 or 1) when sum exceeds 9.
while (l1 != nullptr || l2 != nullptr || carry != 0) {
Continue while there are digits to process OR there's a remaining carry.
int val1 = (l1 != nullptr) ? l1->val : 0;
Get the value from l1's current node, or 0 if l1 is exhausted.
int val2 = (l2 != nullptr) ? l2->val : 0;
Get the value from l2's current node, or 0 if l2 is exhausted.
int sum = val1 + val2 + carry;
Calculate the total sum of both digits plus any carry.
carry = sum / 10;
Calculate new carry: 1 if sum >= 10, otherwise 0.
current->next = new ListNode(sum % 10);
Create a new node with the ones digit and attach it to our result.
current = current->next;
Move the current pointer forward to the newly created node.
if (l1 != nullptr) l1 = l1->next;
Move to the next node in l1 if there is one.
if (l2 != nullptr) l2 = l2->next;
Move to the next node in l2 if there is one.
}
End of while loop.
return dummy->next;
Return the actual result (skip the dummy node which was just a placeholder).
}
End of the function.
Related Problems
Want to Learn More?
Master the fundamentals of linked lists — from basic concepts to memory layout and cache performance. Understanding linked lists is essential for solving countless algorithm problems.
Learn more at SoftwareInLevels →Disclaimer: This problem is for educational purposes. We encourage you to try solving the 'Add Two Numbers' question on LeetCode.