LeetCode 热题 100_两数相加（28_2_中等_C++）(单链表)

题目描述：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入输出样例：

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题解：

解题思路：

思路一（使用原链表存储答案）：
1、通过题目分析，这里的计算方式和我们数学上两数相加的思想是完全一样的。首先将对应位相加（记作sum），sum>=10则进位1(记作carry)，再进行下一位的相加并加上进位（carry）依次进行下去。
注意：
① 当最后还需进位时会多一个结点（如90+10=100，会多一位）
② 我们用l1原链表来存储答案时，当len(l1)>len(l2)时我们最多只需创建一个新结点，来存储最后的进位如①所示。
③ 当 len(l1)<len(l2)我们必须创建len(l2)-len(l1)个新的结点，如果最后进位=1还需创建一个新结点。

2、具体思路如下：
① 定义carry代表进位，sum代表每位的加和。
② 从个位开始依次相加，直到l1和l2中较短的链表。
③ 如果l2中还有未相加的结点，将其连接到l1的末尾。
④ 将此时l1剩下的结点相加。
⑤ 如果相加到最后还有一个进位，则添加一个结点，此节点的val必定是1。

3、复杂度分析：
① 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
② 空间复杂度：O(1)。注意返回值不计入空间复杂度。

思路二（使用新链表存储答案）：
1、思路大致和方法一是相同的，只是这里采用额外的存储空间来存储答案，注意额外空间中每个结点都需创建需和方法一区分开。

2、具体思路如下：
① carry代表进位，sum代表每位的加和，head和tail答案链表的首和尾结点（采用尾插法）。
② 从个位开始依次相加，直到l1和l2中较短的链表
③ l1指向后半部分没有相加的链表，将此时l1链表剩余的部分进行相加（只是在处理进位与剩下结点的相加）。
④ 如果最后还有一个进位，则创建一个新的结点 。
这位博主图画的不错，图解链接请点击此链接

3、复杂度分析
① 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
② 空间复杂度：O(1)。注意返回值不计入空间复杂度。

思路三（补零法：详见下方力扣官方原题和题解）
思路和思路一和思路二类似
例：
1000+1=1001
可转换成 ：
    1000
   +0001
=   1001
只是将1前边为null的转换成0进行相加。

代码实现（思路一（使用原链表存储答案））：

ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2) {
	//carry代表进位，sum代表每位的加和 
	int carry=0,sum=0;
	//使用l1存储答案 
	//head用于存储返回答案的首结点，pre_l1用于记录l1的尾结点 
	ListNode *head=l1,*pre_l1=l1;
	//从个位开始依次相加，直到l1和l2中较短的链表 
	while(l1!=nullptr&&l2!=nullptr){
		sum=l1->val+l2->val+carry;
		carry=sum/10;
		l1->val=sum%10;
		pre_l1=l1;
		l1=l1->next;
		l2=l2->next;
	}
	//如果l2中还有未相加的结点，将其连接到l1的末尾 
	if(l2!=nullptr){
		pre_l1->next=l2;
		l1=l2;
	}
	//将剩下的结点相加 
	while(l1!=nullptr){
		//进位为0时后续结点无需变换,因在原链表进行，注意与方法二区分 
		if(carry==0){
			break;
		}
		sum=l1->val+carry;
		carry=sum/10;
		l1->val=sum%10;
		pre_l1=l1; 
		l1=l1->next;
	}
	
	//如果相加到最后还有一个进位，则添加一个结点，此节点的val必定是1 
	if(carry==1){
		ListNode *newNode=new ListNode(1);
		pre_l1->next=newNode;
	}
	return head; 
}

代码实现（思路二（使用新链表存储答案））：

ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
	//答案链表的首和尾结点 
	ListNode *head=nullptr,*tail=nullptr;
	//carry代表进位，sum代表每位的加和
	int carry=0,sum=0;
	//从个位开始依次相加，直到l1和l2中较短的链表
	while(l1!=nullptr&&l2!=nullptr){
		sum=l1->val+l2->val+carry;
		carry=sum/10;
		if(head==nullptr){
			//注意这里创建结点的方式。 
			head=tail=new ListNode(sum%10);
		}else{
			tail->next=new ListNode(sum%10);
			tail=tail->next;
		}
		l1=l1->next;
		l2=l2->next;
	} 
	//l1指向后半部分没有相加的链表 
	if(l2!=nullptr){
		l1=l2;
	}
	//将剩余的链表进行相加 
	while(l1!=nullptr){
		sum=l1->val+carry;
		carry=sum/10;
		tail->next=new ListNode(sum%10);
		tail=tail->next;
		l1=l1->next;
	}
	//如果最后还有一个进位，则创建一个新的结点 
	if(carry==1){
		ListNode *newNode=new ListNode(1);
		tail->next=newNode;
	}
	return head;
}

以思路二为例完成代码调试

#include<iostream>
#include<vector>
using namespace std;

struct ListNode{
	int val;
	ListNode *next;
	ListNode():val(0),next(nullptr){}
	ListNode(int x):val(x),next(nullptr){}
	ListNode(int x,ListNode *next):val(x),next(next){}
};

//尾插法创建单链表 
ListNode *createList(vector<int> arr){
	ListNode *head=nullptr,*tail=nullptr;
	for(const auto &val:arr){
		ListNode *newNode=new ListNode(val);
		if(head==nullptr){
			head=newNode;
			tail=newNode;
		}else{
			tail->next=newNode;
			tail=newNode;
		}
	}
	return head;
}

//方法二（创建一个新的链表存储答案）
ListNode* addTwoNumbers2(ListNode* l1, ListNode* l2) {
	//答案链表的首和尾结点 
	ListNode *head=nullptr,*tail=nullptr;
	//carry代表进位，sum代表每位的加和
	int carry=0,sum=0;
	//从个位开始依次相加，直到l1和l2中较短的链表
	while(l1!=nullptr&&l2!=nullptr){
		sum=l1->val+l2->val+carry;
		carry=sum/10;
		if(head==nullptr){
			//注意这里创建结点的方式。 
			head=tail=new ListNode(sum%10);
		}else{
			tail->next=new ListNode(sum%10);
			tail=tail->next;
		}
		l1=l1->next;
		l2=l2->next;
	} 
	//l1指向后半部分没有相加的链表 
	if(l2!=nullptr){
		l1=l2;
	}
	//将剩余的链表进行相加 
	while(l1!=nullptr){
		sum=l1->val+carry;
		carry=sum/10;
		tail->next=new ListNode(sum%10);
		tail=tail->next;
		l1=l1->next;
	}
	//如果最后还有一个进位，则创建一个新的结点 
	if(carry==1){
		ListNode *newNode=new ListNode(1);
		tail->next=newNode;
	}
	return head;
}

int main(){
	vector<int> a={9,9,9,9,9,9,9};
	
	vector<int> b={9,9,9,9};
	ListNode *l1=createList(a);
	ListNode *l2=createList(b);
	ListNode *ans=addTwoNumbers2(l1,l2);
	//输出答案
	while(ans!=nullptr){
		cout<<ans->val<<"->";
		ans=ans->next;
	}
	cout<<"next";
	return 0;
} 

LeetCode 热题 100_两数相加（28_2)原题链接
欢迎大家和我沟通交流(✿◠‿◠)