445. Add Two Numbers II
1. Description
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
2. Example
Example 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0]
Output: [0]
3. 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.
4. Follow Up
Could you solve it without reversing the input lists?
5. Solutions
My Accepted Solution
m is the number of nodes in m_l1, n is the number of nodes in m_l2
Time complexity: O(max(m, n))
Space complexity: O(m + n)
class Solution {
public:
// ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
ListNode* addTwoNumbers(ListNode* m_l1, ListNode* m_l2) {
vector<ListNode*> num1Nodes, num2Nodes;
for(auto iter = m_l1; iter; iter = iter->next) {
num1Nodes.push_back(iter);
}
for(auto iter = m_l2; iter; iter = iter->next) {
num2Nodes.push_back(iter);
}
if(num1Nodes.size() < num2Nodes.size()) {
swap(num1Nodes, num2Nodes);
}
auto guardHead = new ListNode();
int carry = 0;
for(int i = num1Nodes.size() - 1, j = num2Nodes.size() - 1; i >= 0; --i, --j) {
num1Nodes[i]->val += (j >= 0 ? num2Nodes[j]->val : 0) + carry;
carry = num1Nodes[i]->val / 10;
num1Nodes[i]->val %= 10;
num1Nodes[i]->next = guardHead->next;
guardHead->next = num1Nodes[i];
}
if(carry > 0) {
auto carryNode = new ListNode(carry);
carryNode->next = guardHead->next;
guardHead->next = carryNode;
}
return guardHead->next;
}
};