Add Two Numbers
LeetCode #2 · Medium · Linked Lists · C++ solution with worked-out approach and complexity analysis.
Approach
Elementary Math (Digit by Digit Addition)
Traverse both lists simultaneously, adding corresponding digits along with carry. Create new nodes for the result. Handle remaining nodes and final carry.
Time
O(max(m, n))
m, n are lengths of the two lists
Space
O(max(m, n))
the result list
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- l1 = [2,4,3], l2 = [5,6,4]
- Output:
- [7,0,8]
- Note:
- 342 + 465 = 807
Example 2
- Input:
- l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
- Output:
- [8,9,9,9,0,0,0,1]
Constraints
- •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
C++ Solution
solution.cpp
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(0); // Dummy head to simplify edge cases
ListNode *curr = &dummy;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int sum = carry;
if (l1 != nullptr) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
}
return dummy.next;
}
};