Q：
A：
这种题的用例是一定会搞一些很大的数的。long都会溢出，所以我们就不用尝试转数字做加法转链表的方法了。另外直接倒置两个链表再做加法的做法会改变原链表，题干也说了禁止改动原链表。
1.求两个链表长度，如果一长一短，把短的前面加若干个0节点，使得两个链表长度相同。之后对于就递归连接链表。dfs函数参数为前一个结果链表指针pre，当前的两个数据链表指针p1、p2。在函数中首先新建节点与pre相连，之后递归p1、p2的后继链表。dfs函数返回的是进位值，1或0。递归函数的进位值返回后要加在当前节点val上，若有进位继续返回给上级节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1==0 and l2==0){
return 0;
}
int len1=0,len2=0;
ListNode* p=l1;
while(p){
++len1;
p=p->next;
}
p=l2;
while(p){
++len2;
p=p->next;
}
p=new ListNode(0);
ListNode* n_head=p;
for(int i=1;i<abs(len1-len2);++i){
ListNode* pre_p=p;
p=new ListNode(0);
pre_p->next=p;
}
if(len1<len2){
p->next=l1;
l1=n_head;
}
else if(len1>len2){
p->next=l2;
l2=n_head;
}
ListNode* res=new ListNode(1); //incase sum of l1 and l2 >9
int c=dfs(res,l1,l2);
if(c==1){
return res;
}
else{
return res->next;
}
}
int dfs(ListNode* pre, ListNode* p1,ListNode* p2){ //return carry
ListNode* cur=new ListNode((p1->val+p2->val)%10);
pre->next=cur;
int carry=(p1->val+p2->val)/10; //carry to be returned
if(p1->next){
if(dfs(cur,p1->next,p2->next)==1){
cur->val=(cur->val+1)%10;
carry=(p1->val+p2->val+1)/10;
}
}
return carry;
}
};
2.用两个栈存两个链表倒序的值。思路是我们做加法是从小位加到大位，故考虑用栈可以方便的倒置位数。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> stack1,stack2;
while(l1){
stack1.push(l1->val);
l1=l1->next;
}
while(l2){
stack2.push(l2->val);
l2=l2->next;
}
ListNode* head=0;
int carry=0;
while(!stack1.empty() or !stack2.empty() or carry){
ListNode* p=new ListNode(carry);
if(!stack1.empty()){
p->val+=stack1.top();
stack1.pop();
}
if(!stack2.empty()){
p->val+=stack2.top();
stack2.pop();
}
if(p->val>9){
p->val=p->val%10;
carry=1;
}
else{
carry=0;
}
p->next=head;
head=p;
}
return head;
}
};