Add Two Numbers
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.
Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9.
- The list represents a number in reverse order (i.e., the number is stored from least significant digit to most).
- The sum of the two numbers will not exceed 1000.
Examples:
Input: [2,4,3] + [5,6,4]
Output: [7,0,8]
Explanation: The first linked list represents the number 342, and the second linked list represents the number 465. Adding these two numbers gives 807, which is represented by the linked list [7,0,8].
Solutions
Iterative Approach
We initialize a dummy head node and set three pointers, p, q, and current, to the heads of the two linked lists and the dummy head. We also initialize a carry variable to 0. Then we traverse the two linked lists. For each pair of nodes, we calculate the sum of the values and the carry. We update the carry and create a new node with the digit value of the sum. We move the current pointer to the next node and update the carry. If there is still a carry after the loop, we create a new node with the carry value.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(0);
ListNode* p = l1, *q = l2, *current = dummyHead;
int carry = 0;
while (p || q) {
int x = (p) ? p->val : 0;
int y = (q) ? q->val : 0;
int sum = carry + x + y;
carry = sum / 10;
current->next = new ListNode(sum % 10);
current = current->next;
if (p) p = p->next;
if (q) q = q->next;
}
if (carry > 0) {
current->next = new ListNode(carry);
}
return dummyHead->next;
}Follow-up:
What if the digits are stored in non-reverse order?
