题解 | #两个链表生成相加链表#
两个链表生成相加链表
http://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
stack<int> a,b;
int a_l=0,b_l=0;
while(head1)
{
a.push(head1->val);
a_l+=1;
head1=head1->next;
}
while(head2)
{
b.push(head2->val);
b_l+=1;
head2=head2->next;
}
int acc=0;
vector<int> ans;
while(!a.empty()&&!b.empty()){
int temp=a.top() + b.top() + acc;
a.pop();
b.pop();
ans.push_back(temp%10);
acc=temp/10;
a_l--;
b_l--;
}
cout<<a_l<<" "<<b_l;
while(!a.empty())
{
int temp=a.top()+acc;
a.pop();
ans.push_back(temp%10);
acc=temp/10;
}
while(!b.empty())
{
int temp=b.top()+acc;
b.pop();
ans.push_back(temp%10);
acc=temp/10;
}
if(acc!=0)
ans.push_back(acc);
// cout<<c;
ListNode* head=new ListNode(-1);
reverse(ans.begin(),ans.end());
ListNode* p=head;
for(int i=0;i<ans.size();i++)
{
p->next=new ListNode(ans[i]);
p=p->next;
}
return head->next;
}
};
