002.Java实现两数相加

2023-12-16 23:23:25

题意

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

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

示例

输入:l1=[2,4,3],l2=[5,6,4]

输出:[7,0,8]

解释:342+465=807

  1. l1 存储的是 2、4、3,也就是整数 342,逆序嘛;
  2. l2 存储的是 5、6、4,也就是整数 465,逆序嘛;
  3. 个位相加为 7(2+5),十位相加为 10(4+6,需要进位),百位相加为 7(3+4),加上进位的 1 就是 8

难度

中等

分析

首先,搞清楚“逆序”是什么。

逆序:从后往前的顺序,比如 123 的逆序是 321。

题目中的示例其实也给出了解释,假如逆序链表 l1 为 [2,4,3],l2 为 [5,6,4],那么 l1 代表的数字就是 342,l2 为 456。

对于还没有学过链表的球友来说,可以通过二哥的 Java 进阶之路中的LinkedList来学习一下链表的数据结构,大体上就这样:a->b->c->d

两数相加,如果不需要进位的话,就是把对应位置的数字相加,比如 342 + 456 = 798,非常简单。

难点就在于,进位该如何处理。

回想一下我们小学曾经学过的加法竖式,如下图。

对于每一位上的数字相加,都有可能产生进位,比如 4 + 6 = 10,那么 1 就是进位,我们需要把它加到下一位的和中即可。

假设两个链表相同位置的数字分别是 addX 和 addY,进位是 up,那么它们的和(sum)就是 addX + addY + up,如果 sum 大于 10 的话,需要进位,那么进位的值就是 sum / 10,而 sum % 10 就是当前位置的数字。

比如说个位 7+8=15(此时进位为 0),由于和大于 10,所以十位的进位就是 1(sum / 10),个位的数字就是 5(sum % 10)。

十位 4+6+1=11(此时进位为 1),由于和大于 10,所以百位的进位就是 1(sum / 10), 十位的数字就是 1(sum % 10)。

百位 3+5+1=9(此时进位为 1),由于和小于 10,所以千位的进位就是 0(sum / 10),百位的数字就是 9(sum % 10)。

也就是说 347(对应的逆序链表为「7、4、3」)+568(对应的逆序链表为「8、6、5」)=915(新的逆序链表为 5、1、9),这就是我们最终的结果。

  1. 7+8=15,进位为 1,个位为 5;
  2. 4+6+1=11,进位为 1,十位为 1;
  3. 3+5+1=9,进位为 0,百位为 9。

是不是突然发现,逆序链表的顺序和我们的计算顺序恰好是一样的,这样子就方便我们直接进行处理。

假如不是逆序的,那么我们就需要先把链表反转,然后再进行计算,最后再把结果反转回来。

妙啊!

/**

*Definitionforsingly-linkedlist.

*public? class? ListNode{

*int? val;

*ListNode? next;

*ListNode(){}

*ListNode(intval){this.val=val;}

*ListNode(int? val,ListNode? next){this.val=val;this.next=next;}

*}

*/

class? Solution{

public? ListNodeaddTwoNumbers( ListNode l1, ListNode l2){

ListNode? dummyHead = new? ListNode(0);//创建一个哨兵节点,方便返回结果

ListNode p = l1,q = l2,curr = dummyHead;//初始化三个指针:p和q分别遍历两个输入链表,curr用于构建结果链表

int carry = 0;//初始化进位值为0



//遍历两个链表直到全部结束

while(p! = null || q! = null){

//获取当前节点的值,如果节点不存在则为0

int x = (p!=null)?p.val:0;

int y = (q!=null)?q.val:0;

//计算两个值和进位值的总和

int? sum = carry + x + y;

//更新进位值

carry = sum/10;

//创建新节点,值为总和的个位数,并将其加入到结果链表

curr.next = newListNode(sum%10);

//移动curr指针到新节点

curr = curr.next;

//如果存在,移动p和q到各自链表的下一个节点

if(p!=null)? p=p.next;

if(q!=null)? q=q.next;

}

//循环结束后,如果仍有进位,则在结果链表末尾添加一个节点

if(carry>0){

curr.next=newListNode(carry);

}

//返回哨兵节点的下一个节点,即结果链表的头节点

return? dummyHead.next;

}

}

当输入是 l1 = [2,4,3] 和 l2 = [5,6,4] 时,我们来模拟一下整个题解过程:

  1. 初始化:创建一个哨兵节点 dummyHead 用于简化边界情况的处理,以及一个临时节点 curr 指向它。设置进位 carry 为 0。
  2. 开始遍历两个链表
  3. 第一轮迭代
  4. l1 的当前元素是 2,l2 的当前元素是 5。
  5. 计算和:sum = 2 + 5 + 0 = 7(当前进位 carry 是 0)。
  6. 创建新节点,值为 sum % 10 = 7,进位 carry = sum / 10 = 0。
  7. 移动 curr 到新节点。
  8. 移动 l1 和 l2 分别到下一个节点。
  9. 第二轮迭代
  10. l1 的当前元素是 4,l2 的当前元素是 6。
  11. 计算和:sum = 4 + 6 + 0 = 10(当前进位 carry 是 0)。
  12. 创建新节点,值为 sum % 10 = 0,进位 carry = sum / 10 = 1。
  13. 移动 curr 到新节点。
  14. 移动 l1 和 l2 分别到下一个节点。
  15. 第三轮迭代
  16. l1 的当前元素是 3,l2 的当前元素是 4。
  17. 计算和:sum = 3 + 4 + 1 = 8(当前进位 carry 是 1)。
  18. 创建新节点,值为 sum % 10 = 8,进位 carry = sum / 10 = 0。
  19. 移动 curr 到新节点。
  20. l1 和 l2 都没有下一个节点,结束遍历。
  21. 检查最后的进位
  22. 检查 carry 是否大于 0。此处 carry = 0,所以不需要添加新节点。
  23. 返回结果
  24. 返回 dummyHead.next,即哨兵节点后的链表。结果为 7 -> 0 -> 8。

342+465=807,我们得到了正确的答案。

时间复杂度:

空间复杂度:

我擦嘞,竟然打败了 100% 的用户!

总结

本题其实是一个铺垫,就比如说给你了一个非常非常大的数,用 int、long 根本无法装下,那其实就可以把这个数简化为一个链表,每个节点存储一个数位,这样子就可以无限扩展了。

其实这道题的内核就是大数相加,只不过我们把大数用链表来表示了,并且题目限制了每个链表中的节点数在范围 [1, 100] 内。

其实计算机中的大多数思想都是这样的,当一个问题超复杂时,我们就简化它,把它拆分成一个个小问题,然后再去解决。

关于 while 循环和链表的知识,我这里补充一下学习资料。

  1. while 循环
  2. 链表(Linked list)
  3. LinkedList 和 ArrayList 的区别

力扣链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

一步一个脚印

不积跬步无以至千里,不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了

文章来源:https://blog.csdn.net/qq_64948664/article/details/135037538
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。