LeetCode (2)：两数相加
source link: https://mp.weixin.qq.com/s/iQE5DZYmaR8JAWT6fBSfow
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 相关的文章：
这次来写一下 LeetCode 的第 2 题，两数相加。
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
上面的题就是 两数相加 题目的截图，同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义，然后在其中实现 两数相加 的解题过程。这次我使用 C 语言来进行完成。
C 语言给出的函数定义如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
}
通过函数定义可以看出，addTwoNumbers 函数的参数是两个单向链表，然后返回值也是一个链表，然后我们要做的就是让两个链表的每个节点相加，并产生新的节点构成一个新的链表，并且链表上的每个节点只能存储一位数。
问题分析
初看题目，可能觉得并不复杂，事实上也的确不是很复杂。两个链表的每个节点相加，然后所得的结果存在一个新的链表节点当中，且这个节点中只能存一位数。
其实，这样的思路是比较符合我们做加法思路的，在我们列竖式的时候，就是按照这种方式来进行计算的。这里用图来进行描述。
只要使链表的指针逐步的移动，并使指针所指向的节点中的值进行相加，相加后判断是否产生进位，如果产生进位则记录下进位的值，把进位后剩下的个位数写入链表的节点，进位的值与当前节点的下对节点相加时同时参与运算即可。
链表最后的一对节点相加后也可能会产生进位，因此在循环相加后，需要判断是否产生了进位，如果有进位需要为这个进位一个单独的节点链到链表的结尾处。
当一个链表比另外一个链表长的时候，只要让较长的那个链表和 0 相加即可。直到两个链表都为空为止。
代码实现
C 语言的代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
struct ListNode* one = l1;
struct ListNode* two = l2;
struct ListNode* sum = NULL;
struct ListNode* tsum = NULL;
/* 进位值 */
int tmp = 0;
struct ListNode* tn = NULL;
while (one != NULL || two != NULL) {
int o = 0, t = 0, s = 0;
if (one != NULL) {
o = one->val;
one = one->next;
}
if (two != NULL) {
t = two->val;
two = two->next;
}
/* 带进位加法 */
s = o + t + tmp;
tmp = s / 10;
s = s % 10;
tn = (struct ListNode*)malloc(sizeof(struct ListNode));
tn->val = s;
tn->next = NULL;
if (sum != NULL) {
tsum->next = tn;
tsum = tn;
} else {
sum = tn;
tsum = tn;
}
}
if (tmp != 0) {
tn = (struct ListNode*)malloc(sizeof(struct ListNode));
tn->val = tmp;
tn->next = NULL;
tsum->next = tn;
}
return sum;
}
提交结果
在写完代码后，点击右下角的 “ 执行代码 ”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体， 如果所有的测试用例都通过了，那么就会给出 “通过” 的字样， 如果没有通过，会给出失败的那一组测试用例，我们可以根据给出的测试用例来继续修改代码 。我们的代码提交后的截图如下：
喜欢就点在看哦~
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK