力扣网 2 两数相加
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 465 = 807.思路分析
最基本的思路，就是将俩链表转正过来，相加后再进行逆序，实现是可以实现，但时间复杂度太高了，此外这里相加还涉及到进位的问题，这样做会很麻烦。
换一种思路，我们直接在现成的两个链表上操作，可以看到，相加后逆过来的值刚好就是对应的两个结点的相加，那我们可以直接遍历两个链表，将对应的值相加，并存放到新的结点里。
需要注意的事项：
1.这里会涉及到进位的问题，我们可以将相加后的值/10得到进位值（大于10的进位值为1，小于10的进位值为0）每次相加时加上进位值即可。
2.还会存在链表结点数不等的情况，我们将不存在的结点数的值视为0即可。
代码语言：javascript复制struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* s1=l1;//遍历链表1的指针
struct ListNode* s2=l2;//遍历链表2的指针
struct ListNode* head=NULL,*tail=NULL;//新链表头结点指针和遍历链表的指针tail
int carry=0;//进位值，最开始等于0
while(s1||s2)//遍历两个链表，两个链表同时为空结束
{
int n1=s1?s1->val:0;//如果s1不为空取s1对应的值，空则视为0
int n2=s2?s2->val:0;//如果s2不为空取s2对应的值，空则视为0
int sum=n1 n2 carry;//和等于n1 n2 进位值
if(head==NULL)//最开始头结点为空
{
head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//动态创建内存赋给头结点和遍历指针
tail->val=sum;//将sum模10的值放到tail中
tail->next=NULL;//tail->next置为空
}
else//头结点不为空的情况
{
tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));//动态创建内存赋给遍历指针的下一个结点
(tail->next)->val=sum;//将sum模10的值赋给下一个结点的值
tail=tail->next;//移动tail
tail->next=NULL;//置空
}
carry=sum/10;//获得新的carry值
if(s1)//s1不为空，s1往下走
{
s1=s1->next;
}
if(s2)s2不为空，s2往下走
{
s2=s2->next;
}
}
if(carry>0)//遍历完成后，如果进位值不为零，还得往后面再添加一个结点存放进位值
{
tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
(tail->next)->val=carry;
tail=tail->next;
tail->next=NULL;
}
return head;//返回头结点
}
