本文介绍: 换一种思路,我们直接在现成的两个链表操作可以看到相加后逆过来的值刚好就是对应的两个结点相加,那我们可以直接遍历两个链表,将对应的值相加,并存放到新的结点里。最基本的思路,就是将俩链表转正过来,相加后再进行逆序实现可以实现,但时间复杂度太高了,此外这里相加还涉及到进位问题,这样做会很麻烦。1.这里会涉及到进位的问题,我们可以相加后的值/10得到进位值(大于10的进位值为1,小于10的进位值为0)每次相加时加上进位即可。2.还会存在链表结点数不等的情况,我们将不存在结点数的值视为0即可

力扣网 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;//返回头结点
}

 

原文地址:https://blog.csdn.net/wcl312/article/details/134600735

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_21782.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注