题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
分析
因为数字是倒着存放的，我们就可以让链表L1和L2表头对齐开始相加。
分为以下几种情况：
1、321+ 521 = 842 最简单的一种 俩个链表一样长还无进位
2、123456 + 213 = 336456 如果L2链表到头了，我们可以直接把L1链表值给到新的链表
3、 9999 + 9999 = 89991 链表多一个长度存放了最高位的进位。
4、999999 + 99 = 8990001 就算是只有一个链表也可能因为前面的一个进位导致最后还要进位
设置一个进位标志ret，创建一个头节点head（头节点不存放数据），再创建俩个链表的指针，用于
遍历找val。实现如下：
int ret = 0;//进位 0-无 1-有
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建头节点
struct ListNode* h = head;//创建头指针
struct ListNode* p = l1;//表1指针
struct ListNode* q = l2;//表2指针
代码如下：
C
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ int ret = 0;//进位 0-无 1-有 struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建头节点 struct ListNode* h = head;//创建头指针 struct ListNode* p = l1;//表1指针 struct ListNode* q = l2;//表2指针 while(p != NULL || q != NULL || ret == 1) { //p和q只要没指向NULL就表示还有数据 //ret == 1 最后有进位，就会多出一位 如500+520=1020 int tmp = ret;//保存当前俩链表的val以及进位之和 if(p != NULL) { tmp += p->val; p = p->next;//指针向后移动 } if(q != NULL) { tmp += q->val; q = q->next; } if(tmp > 9)//需要进位 { ret = 1; tmp = tmp - 10; } else { ret = 0;//不需要进位，就把ret置为空 } struct ListNode* st = (struct ListNode*)malloc(sizeof(struct ListNode));//创建新节点 st->val = tmp;//赋值 h->next = st;//连接新节点 h = h->next;//定位到新节点 } h->next = NULL;//最后指向空节点 return head->next;//头节点不存数据，返回下一个 }
运行效率
C++
/** * Definition for singly-linked list-> * 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) { int ret = 0;//进位标志 ListNode* head = new ListNode(0); ListNode*h = head; ListNode* p = l1; ListNode* q = l2; while(p != NULL || q != NULL || ret == 1) { int num = ret; if(p != NULL) { num += p->val; p = p->next; } if(q != NULL) { num += q->val; q = q->next; } if(num > 9) { num -= 10; ret = 1; } else { ret = 0; } ListNode* ln = new ListNode(num); h->next = ln; h = h->next; } h->next = NULL; return head->next; } };
本节完
