利用栈求解
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
stack<ListNode*> stack1;
stack<ListNode*> stack2;
stack<ListNode*> resultStack;
ListNode* result = nullptr;
ListNode* cur = nullptr;
while (head1) {
stack1.push(head1);
head1 = head1->next;
}
while (head2) {
stack2.push(head2);
head2 = head2->next;
}
// 进位
int tmp = 0;
while (!stack1.empty() || !stack2.empty()) {
int num1 = 0;
int num2 = 0;
if (!stack1.empty()) {
num1 = stack1.top()->val;
stack1.pop();
}
if (!stack2.empty()) {
num2 = stack2.top()->val;
stack2.pop();
}
int sumNum = num1 + num2 + tmp;
ListNode* tmpNode = new ListNode(sumNum % 10);
tmp = sumNum / 10;
resultStack.push(tmpNode);
}
// 进位
if (tmp > 0) {
ListNode* tmpNode = new ListNode(tmp);
tmpNode->next = nullptr;
tmp = 0;
resultStack.push(tmpNode);
}
while (!resultStack.empty()) {
if (result) {
cur->next = resultStack.top();
cur = cur->next;
resultStack.pop();
}
else {
result = cur = resultStack.top();
resultStack.pop();
}
}
return result;
}
};