Problem Statement
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.
Sample Input
l1 = [7,2,4,3], l2 = [5,6,4]
Sample Output
[7,8,0,7]
Link to question: https://leetcode.com/problems/add-two-numbers-ii/
Solution (Java)
/**
* Definition for singly-linked list.
* 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) {
stack<int> n1, n2, sum;
ListNode *res=new ListNode();
ListNode *cur=res;
ListNode *prev;
int carry=0;
while(l1!=nullptr) {
n1.push(l1->val);
l1=l1->next;
}
while(l2!=nullptr) {
n2.push(l2->val);
l2=l2->next;
}
while(!(n1.empty() && n2.empty())) {
if(n1.empty()) {
sum.push((n2.top()+carry)%10);
carry=(n2.top()+carry)/10;
n2.pop();
}
else if(n2.empty()) {
sum.push((n1.top()+carry)%10);
carry=(n1.top()+carry)/10;
n1.pop();
}
else {
sum.push((n2.top()+n1.top()+carry)%10);
carry=(n1.top()+n2.top()+carry)/10;
n1.pop();
n2.pop();
}
}
if(carry!=0)
sum.push(carry);
while(!sum.empty()) {
cur->val=sum.top();
cur->next=new ListNode();
prev=cur;
cur=cur->next;
sum.pop();
}
prev->next=nullptr;
return res;
}
};
Explanation
Firstly, push the numbers from both the linked lists into two separate stacks. This will store the linked list in reverse order and will also help in doing the addition operation. Now pop the elements from the stacks and add them and push the modulo 10 of the sum in the third stack and store the quotient 10 of sum in the carry (simple mathematical addition, just as we used to do in kindergarten). Lastly popped the elements from the third stack and inserted into the third linked list and that will the resultant linked list.
Top comments (0)