Problem : 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0] Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Solution
This problem requires you to be familiar with Linked list. Once you understand the linked list, this problem can be solved with simple math operations.
For example,
List 1 = {2, 4, 9}
List 2 = {5, 6, 4, 9]
The sum would be :
5+2 = 7
4+6 = 10 = 0 and 1 carry
9+1 + 1 (carried) = 14 = 4
9 + 1 (carried) = 10
So in reverse order = 70401 is the sum.
To get sum value and carry value, you can do as follows:
In above example, total sum was 14 at one point, so if you want to get the value, you simply have to divide by 10.
14%10 = 4 (value)
14/10 = 1 (carry).
Pseudocode
1. Initialize current node to dummy head of the returning node.
2. initialize carry = 0
3. Loop through list1 and list2 until you reach both ends of list and carry =0
set x to node list1 value, if not 0 by default
set y to node list2 value, if not 0 by default
set sum = x+y; //For example, 2 + 5 = 7
update carry = sum/10
create a new node with digit value of sum%10 and set current's next, then advance to next.
assign next node to get next value of list1 and list2.
Implementation
ListNode* AddTwoNumbers(ListNode* l1, ListNode *l2){
int carry = 0;
int sum;
ListNode *head = new ListNode(0);
ListNode *current_node = head;
while(l1 != nullptr || l2 != nullptr || carry == 1){
int num1 = l1 ? l1->val : 0;
int num2 = l2 ? l2->val : 0;
sum = carry == 1 ? num1 + num2 + 1 : num1 + num2;
carry = 0;
if(sum/10 >= 1){
carry = 1;
sum = sum%10;
current_node->next = new ListNode(sum);
current_node = current_node->next;
}else{
current_node->next = new ListNode(sum);
current_node = current_node->next;
}
l1 = l1? l1->next : nullptr;
l2 = l2? l2->next : nullptr;
}
return head->next;
}
If you want to check the full source code, you can check it here:
I also implemented whole source code another way, by adding insert node methods as well, you can check that here:
If you have any other questions or suggestions to improve my code, please feel free to comment below. thank you.
0 Comments