两数相加

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

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

你可以假设除了数字 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. 先将l1和l2头节点的值加起来赋值给新链表的头节点 遍历两个链表，只要有一个链表还没有遍历到末尾，就继续遍历
2.每次遍历生成一个当前节点cur的下一个节点，其值为两链表对应节点的和再加上当前节点cur产生的进位 更新进位后的当前节点cur的值
3. 循环结束后，因为首位可能产生进位，因此如果cur.val是两位数的话，新增一个节点 返回头节点

#include<iostream>
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) {}
  };
 
class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
	{
		//用来存放相加结果的链表
		ListNode* head = new ListNode(l1->val+l2->val);//头指针指向第一个节点,第一个节点的val值是l1的个位加上l2的个位
		//head链表的移动指针
		ListNode* cur = head;
		//l1的移动指针
		ListNode* p1 = l1;
		//l2的移动指针
		ListNode* p2 = l2;
		//如果l1的长度较短，那么就在l2多出l1的位数补上0
		//例如:l1--->123   l2---->123456 ，那么l1补上0后的结果为123000,    l1+l2=123000+123456
		//因此循环结束的条件是l1和l2都为空
		while (p1->next!= NULL || p2->next!= NULL)
		{
			//如果l1->next!=NULL，那么p1=l1->next,否则就说明l1位数少，需要补上0
			//p1=l1->next是对l1链表的每个节点进行遍历，获得当前节点上的数字
			p1 = p1->next != NULL ? p1->next : new ListNode();//如果l1的位数较少，那么就在他最高位前面补上0,方便与l2进行相加操作
			p2 = p2->next != NULL ? p2->next : new ListNode();
			//生成head链表新的一个节点，用来存放当前遍历得到的l1+l2的val值
			//例如第一次循环获得的是l1和l2的十位上数字相加之和
			//这里还要加上cur指向当前节点的val值/10，是因为
			//例如：第一个两个整数个位相加得到的val=12,那么此时要进位，这里是尾插法，cur的next新节点存放的值是十位的值，因此12/10=1,那么十位进1
			cur->next = new ListNode(p1->val + p2->val+cur->val/10);
			//上个例子说到,cur的个位得到的之和为12，上面十位进1后，个位不应该再存储12，而应该是2,因此12%10=2
			cur->val %= 10;
			//再完成了进位操作后，cur指针就可以后移到十位
			cur = cur->next;
		}
		//如果循环结束后，cur的val值大于等于10,比如910+210,最后9+2=11，大于10，因此应该还要再进一位，到千位
		if (cur->val >= 10)
		{
			cur->next = new ListNode(cur->val/10);//因为还要再次前进一位到千位，所以还要再次开辟一个新节点，存放千位
			cur->val %= 10;//当前百位的11，再进位结束后，应该变为1
		}
		return head;
	}
};
//测试-----------------------------
ListNode* input(ListNode* l)
{
	cout << "请为当前链表赋值：" << endl;
	int num = 0;
	cin >> num;
	l->val = num;
	if (num == 0)
		return l;
	while (1)
	{
		cin >> num;
		if (num == 0)
			return l;
		ListNode* newNode = new ListNode;
		newNode->val = num;
		newNode->next = l;
		l = newNode;
	}
	return l;
}
//遍历链表
void display(ListNode* l)
{
	if (l == NULL)
		return;
	ListNode* move = l;
	cout << "遍历输出链表：" << endl;
	while (move)
	{
		cout << move->val;
		move = move->next;
	}
	cout << endl;
}
void test()
{
	ListNode* l1 = new ListNode;
	l1=input(l1);
	display(l1);
	ListNode* l2 = new ListNode;
	l2 = input(l2);
	display(l2);
	Solution s;
	ListNode* head =s.addTwoNumbers(l1, l2);
	//遍历head链表
	ListNode* p = head;
	int ret[10] = { 0 };
	int i = 0;
	//遍历head链表时，要逆序遍历，输出正确的顺序
	while (p)
	{
		ret[i] = p->val;
		i++;//顺便记录到底存储了几位数字
		p = p->next;
	}
	cout << i << "位数字" << endl;
	for (int j = i-1; j >= 0; j--)
	{
		cout << ret[j];
	}
}
int main()
{
	test();
	cout << endl;
	system("pause");
	return 0;
}

单链表逆序遍历的递归写法

//递归遍历
void output(ListNode* head)
{
	if (head == NULL)
		return;
	output(head->next);
	cout << head->val ;
}

加法模板

<公式>

当前位 = (A 的当前位 + B 的当前位 + 进位carry) % 10 注意，AB两数都加完后，最后判断一下进位 carry,
进位不为 0 的话加在前面。

<加法模板>

while ( A 没完 || B 没完)
A 的当前位
B 的当前位

和 = A 的当前位 + B 的当前位 + 进位carry

当前位 = 和 % 10;
进位 = 和 / 10;
判断还有进位吗