题意概述

• 给定两个链表，每个链表从头至尾依次代表一个整数的从高位到低位，即每个链表代表一个整数
• 要求生成一个新链表，新链表的代表的整数为题中两个链表的和

方法一：反转链表后按位加

思路与具体做法

• 因为单链表的遍历，只能从头至尾。而每个链表从头至尾依次代表一个整数的从高位到低位，即我们需要不断从链表尾处取出结点权值来完成对应位的相加，这样不好操作，所以我们先反转链表，简化操作
• 接着在两个链表有结点时，依次取出两个链表的对应位相加，大于10的数还要考虑进位，然后根据加和新建链表
• 注意取完两个链表的结点时，可能会产生进位，如有进位则再次新建一个结点即可

class Solution {
public:
    ListNode* reverse(ListNode* head){//反转链表 
        ListNode* p=head,*pre=NULL,*next=p->next;
        while(p){
            p->next=pre;//反转next指针
            pre=p;
            p=next;
            next=p->next;
        }
        return pre;//返回反转后的头指针 
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode *p1=reverse(head1);//反转链表 
        ListNode *p2=reverse(head2);
		ListNode *list=new ListNode(0);//新建链表 
		ListNode *p=list;//头指针 
        int carry=0;
        while(p1||p2){//两个链表有结点时 
        	int sum=carry;//对应位累加的和  
        	if(p1){//取出对应位
        		sum+=p1->val;
        		p1=p1->next;
			}
        	if(p2){//取出对应位
        		sum+=p2->val;
        		p2=p2->next;
			}
			if(sum>=10)carry=1,sum%=10;//处理进位 
			else carry=0;
			ListNode* t=new ListNode(sum);//头插法建立单链表 
			t->next=p->next;
			p->next=t;			
		}
		if(carry){//若最后还有进位 
			ListNode* t=new ListNode(carry);//头插法建立单链表
			t->next=p->next;
			p->next=t;			
		}
        return list->next;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(m+n)O(m+n)$O(m+n)，遍历两个链表的全部位置
• 空间复杂度：$O\left(max\right(m,n\left)\right)O(max(m,n))$O(max(m,n))，新建了长度为max(m,n)的结果链表

方法二：双栈

思路与具体做法

• 根据栈先入后出的特性，实现对链表权值的逆序访问，即出栈顺序为个位，十位，百位...
• 接着在两个栈非空时，依次取出两个栈的对应数相加，大于10的数还要考虑进位，然后根据加和新建链表
• 注意取完两个链表的结点时，可能会产生进位，如有进位则再次新建一个结点即可

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
    	stack<int>s1,s2;//保存原链表中的数 
        while(head1){//遍历原链表 
        	s1.push(head1->val);
        	head1=head1->next;
		} 
        while(head2){
        	s2.push(head2->val);
        	head2=head2->next;
		} 
		ListNode* list=new ListNode(0);//新建链表 
		ListNode* p=list;//头指针 
		int carry=0;//进位标记 
		while(!s1.empty()||!s2.empty()){//在两个栈都不为空时 
			int sum=carry;//对应位累加的和 
			if(!s1.empty()){//取出对应位 
				sum+=s1.top();s1.pop();
			}
			if(!s2.empty()){//取出对应位 
				sum+=s2.top();s2.pop();
			}
			if(sum>=10)carry=1,sum%=10;//处理进位 
			else carry=0;
			ListNode* t=new ListNode(sum);//头插法建立单链表 
			t->next=p->next;
			p->next=t;
		}
		if(carry){//若最后还有进位 
			ListNode* t=new ListNode(carry);//头插法建立单链表
			t->next=p->next;
			p->next=t;			
		}
		return list->next;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(m+n)O(m+n)$O(m+n)，按序遍历两个链表的全部位置
• 空间复杂度：$O(m+n)O(m+n)$O(m+n)，辅助栈的总深度为m+n