力扣网 2 两数相加

题目描述

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

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

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

思路分析

最基本的思路，就是将俩链表转正过来，相加后再进行逆序，实现是可以实现，但时间复杂度太高了，此外这里相加还涉及到进位的问题，这样做会很麻烦。

换一种思路，我们直接在现成的两个链表上操作，可以看到，相加后逆过来的值刚好就是对应的两个结点的相加，那我们可以直接遍历两个链表，将对应的值相加，并存放到新的结点里。

需要注意的事项：

1.这里会涉及到进位的问题，我们可以将相加后的值/10得到进位值（大于10的进位值为1，小于10的进位值为0）每次相加时加上进位值即可。

2.还会存在链表结点数不等的情况，我们将不存在的结点数的值视为0即可。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* s1=l1;//遍历链表1的指针
    struct ListNode* s2=l2;//遍历链表2的指针
    struct ListNode* head=NULL,*tail=NULL;//新链表头结点指针和遍历链表的指针tail
    int carry=0;//进位值，最开始等于0
    while(s1||s2)//遍历两个链表，两个链表同时为空结束
    {
        int n1=s1?s1->val:0;//如果s1不为空取s1对应的值，空则视为0
        int n2=s2?s2->val:0;//如果s2不为空取s2对应的值，空则视为0
        int sum=n1+n2+carry;//和等于n1+n2+进位值
        
        if(head==NULL)//最开始头结点为空
        {
            head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//动态创建内存赋给头结点和遍历指针
            tail->val=sum%10;//将sum模10的值放到tail中
            tail->next=NULL;//tail->next置为空
        }
        else//头结点不为空的情况
        {
            tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));//动态创建内存赋给遍历指针的下一个结点
            (tail->next)->val=sum%10;//将sum模10的值赋给下一个结点的值
            tail=tail->next;//移动tail
            tail->next=NULL;//置空
        }
        carry=sum/10;//获得新的carry值
        if(s1)//s1不为空，s1往下走
        {
            s1=s1->next;
        }
        if(s2)s2不为空，s2往下走
        {
            s2=s2->next;
        }
    }
    if(carry>0)//遍历完成后，如果进位值不为零，还得往后面再添加一个结点存放进位值
    {
        tail->next=(struct ListNode*)malloc(sizeof(struct ListNode));
        (tail->next)->val=carry;
        tail=tail->next;
        tail->next=NULL;
    }
    return head;//返回头结点
}