本文介绍: 换一种思路,我们直接在现成的两个链表上操作,可以看到,相加后逆过来的值刚好就是对应的两个结点的相加,那我们可以直接遍历两个链表,将对应的值相加,并存放到新的结点里。最基本的思路,就是将俩链表转正过来,相加后再进行逆序,实现是可以实现,但时间复杂度太高了,此外这里相加还涉及到进位的问题,这样做会很麻烦。1.这里会涉及到进位的问题,我们可以将相加后的值/10得到进位值(大于10的进位值为1,小于10的进位值为0)每次相加时加上进位值即可。2.还会存在链表结点数不等的情况,我们将不存在的结点数的值视为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进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。