题解 | #链表相加(二)#
链表相加(二)
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if(!head1) return head2;
if(!head2) return head1;
/*head1 = reverse(head1);
head2 = reverse(head2);
ListNode* p1 = head1;
ListNode* p2 = head2;
ListNode* res = new ListNode(-1);
ListNode* p3 = res;
int m = 0;
while(p1!=NULL||p2!=NULL){
int val1 = p1==NULL ? 0:p1->val;
int val2 = p2==NULL ? 0:p2->val;
int sum =val1 + val2 +m;
m = sum / 10;
sum = sum % 10;
ListNode* temp = new ListNode(sum);
p3->next = temp;
p3 = temp;
if(p1!=NULL) p1 = p1->next;
if(p2!=NULL) p2 = p2->next;
cout<<temp->val<<" ";
}
if(m!=0){
ListNode* temp = new ListNode(m);
p3->next = temp;
}
res = reverse(res->next);
return res;
}
ListNode* reverse(ListNode* head){
if(!head) return NULL;
ListNode* pre = nullptr;
ListNode* nex;
ListNode* cur = head;
while(cur){
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
*/
//栈方法
stack<int> s1;
stack<int> s2;
stack<int> s3;
ListNode* cur = head1;
while(cur->next!=NULL){
s1.push(cur->val);
cur = cur->next;
}
s1.push(cur->val);
cur->next = head2;
cur = cur->next;
while(cur!=NULL){
s2.push(cur->val);
cur = cur->next;
}
int m = 0;
while(!s1.empty() || !s2.empty()){
int val1;
int val2;
if(!s1.empty()){
val1 = s1.top();
s1.pop();
}
else{
val1 = 0;
}
if(!s2.empty()){
val2 = s2.top();
s2.pop();
}
else{
val2 = 0;
}
int sum = val1 + val2 + m;
m = sum / 10;
sum = sum % 10;
s3.push(sum);
}
if(m!=0){
s3.push(m);
}
ListNode* res = head1;
while(!s3.empty()){
head1->val = s3.top();
s3.pop();
if(s3.empty()) break;
head1 = head1->next;
}
head1->next = nullptr;
return res;
}
};
