LeetCode2.两数相加

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

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

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

解题思路：

这题思路比较简单，但也需要注意一些细节，比如动态内存开辟的时候，指针不能指向错了，最后一个结点需要指向空指针等。

刚开始的想法是先将原有的两个数相加的结果给算出来，用int类型元素存储，然后再在堆区开辟空间，倒序存放每一位数，后来提交发现只能通过几百个用例，原因就是累加的结果超出了整型值范围，所以把int改为long long，提及后能通过更多用例，但是也不能AC，这个时候再仔细重读了一下题目，原来有可能出现100位的数，肯定不能用这种方法了。

但那就更简单了，只需要把相应位置的数相加再加上进位，得到的数如果大于等于10，就产生进位，否则不进位，进位的那位数，需要减10存储，然后更新进位标志为1，不进位的直接存储，进位标志置0即可。会出现相加的两个数位数不同的情况，此时以较小数为标准，在该数的位数结束之前，需要两数相加+进位，在此之后，只需要较大数的相应位+进位即可；所有位数加完后还需要检验进位是否为1，是1就需要再开辟一个空间存放，否则不需要，二者最后都要指向空指针。

代码如下：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    int i=0,j=0,k=0,flag=0,tmp;
    char num1[100],num2[100];
    struct ListNode *p0,*p1,*p2;
    p1=l1;
    while(p1!=NULL)
    {
        num1[i++]=p1->val+'0';
        p1=p1->next;
    }
    num1[i]='\0';
    p1=l2;
    while(p1!=NULL)
    {
        num2[j++]=p1->val+'0';
        p1=p1->next;
    }
    num2[j]='\0';
    p2=p1=p0=malloc(sizeof(struct ListNode));
    while(num1[k]!='\0'&&num2[k]!='\0')
    {
        tmp=num1[k]+num2[k]-2*'0'+flag;
        if(tmp>=10)
        {
            flag=1;
            tmp-=10;
        }
        else
        {
            flag=0;
        }
        p1=p2;
        p1->val=tmp;
        p1->next=malloc(sizeof(struct ListNode));
        p2=p1->next;
        k++;
    }
    if(num1[k]=='\0'&&num2[k]!='\0')
    {
        while(num2[k]!='\0')
        {
            tmp=num2[k]-'0'+flag;
            if(tmp>=10)
            {
                flag=1;
                tmp-=10;
            }
            else
            {
                flag=0;
            }
            p1=p2;
            p1->val=tmp;
            p1->next=malloc(sizeof(struct ListNode));
            p2=p1->next;
            k++;
        }
    }
    else if(num1[k]!='\0'&&num2[k]=='\0')
    {
        while(num1[k]!='\0')
        {
            tmp=num1[k]-'0'+flag;
            if(tmp>=10)
            {
                flag=1;
                tmp-=10;
            }
            else
            {
                flag=0;
            }
            p1=p2;
            p1->val=tmp;
            p1->next=malloc(sizeof(struct ListNode));
            p2=p1->next;
            k++;
        }     
    }
    if(flag)
    {
        p1=p2;
        p1->val=1;
    }
    p1->next=NULL;
    return p0;
}