https://leetcode.com/problems/add-two-numbers-ii/description/
Solution 1. Read the value to 2 vectors.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
vector<int> v1, v2;
ListNode* ln, * res = nullptr;
ln = l1;
while(ln) {
v1.push_back(ln->val);
ln = ln->next;
}
ln = l2;
while(ln) {
v2.push_back(ln->val);
ln = ln->next;
}
int NI = v1.size(), NJ = v2.size(), c = 0;
for(int i=NI-1, j=NJ-1; i>=0||j>=0|| c; i--, j--, c/=10) {
if(i>=0) c+=v1[i];
if(j>=0) c+=v2[j];
ln = new ListNode(c%10);
ln->next = res;
res = ln;
}
return res;
}
Or use a stack:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1;
stack<int> s2;
ListNode* l = l1, * res=nullptr;
while(l){
s1.push(l->val);
l = l->next;
}
l = l2;
while(l) {
s2.push(l->val);
l = l->next;
}
l = nullptr;
int c = 0;
while(!s1.empty() || !s2.empty() || c) {
if(!s1.empty()) {
c += s1.top();
s1.pop();
}
if(!s2.empty()) {
c += s2.top();
s2.pop();
}
l = new ListNode(c%10);
l->next = res;
res = l;
c /= 10;
}
return res;
}
No comments:
Post a Comment