力扣|两数相加

先放题目：

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

---

下面是解析

我自己其实和官方给出的理解差不多，就是做一个求和，如果两个链表的长度不一致，就认为较短的链表高位均为0

基本思路就是创建一个链表，每一位保存进位标志和数1数2那一位分别对应的数值的和，然后更新进位标志，代码就借用官方给的了：

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {struct ListNode *head = NULL, *tail = NULL;int carry = 0;while (l1 || l2) {int n1 = l1 ? l1->val : 0;int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + carry;if (!head) {head = tail = malloc(sizeof(struct ListNode));tail->val = sum % 10;tail->next = NULL;} else {tail->next = malloc(sizeof(struct ListNode));tail->next->val = sum % 10;tail = tail->next;tail->next = NULL;}carry = sum / 10;if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}if (carry > 0) {tail->next = malloc(sizeof(struct ListNode));tail->next->val = carry;tail->next->next = NULL;}return head;
}

接下来细细解释：

首先是链表的运用

链表在初始化一个节点的时候，用的语句是

struct ListNode *head = NULL, *tail = NULL;
head = tail = malloc(sizeof(struct ListNode));

一般来说，每一次新建一个节点，都要顺手设置为NULL，保持良好的编程习惯

但是只是声明变量时是没有分配存储空间的，要用malloc分配对应的存储空间

之后，我们需要建立进位标识，因为加法会出现进位，进位标识的值应当是和除以10的余数

int carry = 0;
carry = sum / 10;

和来自于这一位对应求和加上进位：

int sum = n1 + n2 + carry;

重中之重是链表的使用，每一节点的next参数，储存下一节点的位置，也就是通过next访问下一节点

在和链表为空时，我们需要首先给链表分配一个空间，并完成链表的初始赋值，设置下一节点为NULL：

head = tail = malloc(sizeof(struct ListNode));
tail->val = sum % 10;
tail->next = NULL;

等到链表中有了一个节点，接下来分配存储空间的时候，就可以直接指定next为新节点的坐标：

tail->next = malloc(sizeof(struct ListNode));

然后对新节点进行赋值，必须始终记得设置next为NULL；

tail->next->val = sum % 10;
tail = tail->next;
tail->next = NULL;

最后判断两个链表到了什么位置，是否到了链表结尾：

if (l1) {l1 = l1->next;}
if (l2) {l2 = l2->next;}

在这个逻辑里面，如果第一个链表到了结尾，就将另一个链表向后移动，

这样，结合循环开头的代码：

int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;

会将已经到结尾的链表对应的n设置为0，另一个正常读取

最后看是否有进位：

if (carry > 0) {tail->next = malloc(sizeof(struct ListNode));tail->next->val = carry;tail->next->next = NULL;
}

程序结束。