给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode） 2. 两数相加
链接：https://leetcode-cn.com/problems/add-two-numbers/
法一：（执行时间12ms）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
if(l1 == NULL || l2 == NULL) return NULL;
struct ListNode head; //新链表的头
head.next = (struct ListNode*)malloc(sizeof(struct ListNode));//创建第一个存储数据的节点
struct ListNode *pCur = &head; //用于遍历创造新节点
int flg = 0; //标记大于１０之后进位
/* 三种情况，即l1不为空时， l2不为空时，都不为空时 。剩下一种情况都为空，退出循环*/
while( (l1 != NULL && l2 != NULL) || (l1 == NULL && l2 != NULL) || (l1 != NULL && l2 == NULL) )
{
pCur = pCur -> next; //更新节点
if(l1 == NULL) pCur -> val = l2->val + flg;
else if(l2 == NULL) pCur -> val = l1->val + flg;
else pCur -> val = l1->val + l2->val + flg;
/* 每次多创建一个结点，在跳出循环后确定最后一个结点是否保留 */
pCur -> next = (struct ListNode*)malloc(sizeof(struct ListNode)); //创造下一个数据节点
if(pCur -> val >= 10) //进位情况
{
pCur -> val %= 10;
flg = 1;
}
else
{
flg = 0;
}
if(l1 != NULL) l1 = l1 -> next;
if(l2 != NULL) l2 = l2 -> next;
}
if(flg == 1) //结束循环后检查是否有进位的数
{
pCur = pCur -> next;
pCur -> val = 1;
pCur -> next = NULL;
}
else //删除多余节点
{
free(pCur->next);
pCur->next = NULL;
}
return head.next; //由于题设采取的是头结点也存储数据的方式，因此在这里直接返回第一个数据结点
}法二：（来源于力扣、执行时间８ms）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode *res = NULL, *p1 = NULL, *p2 = NULL, *p = NULL, *tem_p = NULL;
int num, decade, bit, tem_val = 0;
res = (struct ListNode*)malloc(sizeof(struct ListNode));
p1 = l1;
p2 = l2;
num = p1->val + p2->val;
if(num >= 10)
{
decade = num / 10;
bit = (int)num % 10;
res->val = bit;
tem_val = decade;
res->next = NULL;
}
else
{
res->val = num;
res->next = NULL;
}
p = res;
p1 = p1->next;
p2 = p2->next;
while(1)
{
if(NULL != p1 || NULL != p2)
{
tem_p = (struct ListNode*)malloc(sizeof(struct ListNode));
if(NULL == p1)
{
num = 0 + p2->val + tem_val;
tem_val = 0;
p2 = p2->next;
}
else if(NULL == p2)
{
num = p1->val + 0 + tem_val;
tem_val = 0;
p1 = p1->next;
}
else
{
num = p1->val + p2->val + tem_val;
tem_val = 0;
p1 = p1->next;
p2 = p2->next;
}
if(num >= 10)
{
decade = num / 10;
bit = (int)num % 10;
tem_p->val = bit;
tem_p->next = NULL;
tem_val = decade;
p->next = tem_p;
p = tem_p;
}
else
{
tem_p->val = num;
tem_p->next = NULL;
p->next = tem_p;
p = tem_p;
}
}
else if (0 == tem_val)
{
break;
}
else
{
tem_p = (struct ListNode*)malloc(sizeof(struct ListNode));
tem_p->val = tem_val;
tem_p->next = NULL;
p->next = tem_p;
break;
}
}
return res;
}法三：（来源于力扣、执行时间４ms）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int c=0;
struct ListNode *head,*cur,*next;
head=(struct ListNode *)malloc(sizeof(struct ListNode));
head->next=NULL;
cur=head;
while(l1!=NULL||l2!=NULL||c)
{
next=(struct ListNode *)malloc(sizeof(struct ListNode));
next->next=NULL;
cur->next=next;
cur=next;
l1!=NULL?(c+=l1->val,l1=l1->next):(c+=0);
l2!=NULL?(c+=l2->val,l2=l2->next):(c+=0);
cur->val=c%10;
c=c/10;
}
struct ListNode *del=head;
head=head->next;
free(del);
return head;
}