从零打卡leetcode之day2--两数相加
深知自己在算法方面上很菜,于是打算通过打卡的方式,逼自己一把。每天在leetcode上打卡,并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路,那么,别犹豫了,上车吧,一起学习一起探讨。
题目描述: 给定两个非空链表来表示两个非负整数。 位数按照逆序方式存储, 它们的每个节点只存储单个数字。 将两数相加返回一个新的链表。 你可以假设除了数字 0 之外, 这两个数字都不会以零开头。 示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
我靠,居然还用到了链表的知识,突然就想起了当初用c语言自学链表的那段日子,真的差点被搞死。各种指针指来指去的。
好吧,我这里需要声明一下,如果你还没接触过链表,或者对链表超级不熟悉,麻烦你先去学好链表再来刷题,因为,链表是真的贼重要啊。
方法1:
说实话,看到这道题的时候,我的想法是不管三七二十一,直接把链表代表的数字给直接算出来,然后在把两个数字给加起来,最后在把得到的和拆分成链表。可谓是暴力思路又简单啊。不过感觉代码量会有点多。
例如:
(2 -> 4 -> 3) => 2 + 4 * 10 + 3 * 100 = 342 (5 -> 6 -> 4) => 5 + 6 * 10 + 4 * 100 = 465 然后342 + 465 = 807 接着807 => 7 -> 0 -> 8
代码如下所示:
先给出链表的结构
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
//方法1 public ListNode addTwoNumbers1(ListNode l1, ListNode l2) { int num1 = 0;//用来存放第一个链表代表的数字 int num2 = 0;//用来存放第二个链表代表的数字 int sum = 0;//存放和 //t = 1,10,100....用来代表链表中的个位,十位,百位... int t = 1;//因为是从个位开始遍历的,所以初值为1 //算第一个数字 while(l1 != null){ num1 = num1 + l1.val * t; t = t * 10; l1 = l1.next; } t = 1; //算第二个数字 while(l2 != null){ num2 = num2 + l2.val * t; t = t * 10; l2 = l2.next; } //相加 sum = num1 + num2; //拆分出来放进链表里; ListNode head = null;//作为链表的头节点 ListNode temp = head;//跟踪链表 while(sum > 0) {//结束条件为sum等于0 if(head == null){ head = new ListNode(sum % 10); temp = head; }else{ temp.next = new ListNode(sum % 10); temp = temp.next; } sum = sum / 10; } //由于有可能sum一开始就为0,所以还需要在检查一下 if(head == null){ head = new ListNode(0); } return head; }
大家一起探讨探讨,你们觉得这种思路可行吗?觉得可行的举个爪,不可行的站起来说说为啥不可行。
反正,我是觉得不可行,为什么?
因为题目并没有说这条链表有多长啊,假如这条链表很长的话,一个int型整数根本存不了这个数字,当然,你可能会说,我可以用long long啊。 不好意思,long long也可能存不了。你可能又会说,java或python什么的,不是有大整数咪?好吧,我没去用过这些大整数,不知道具体个什么情况,所以当作没有这么一回事处理,haha。有兴趣的可以去尝试一下。
方法2
刚才方法1已经被告知不可行了。实际上,这道题我是觉得在解法思路上还是比较简单的,我相信大家也都能想到方法2这种方法:
就是我们可以让两个数的个位数相加,十位数相加….然后个位数有进位的话,再把进位给十位数….
例如:
(1 -> 4 -> 5) + (1 -> 6 -> 4 -> 5) (我是故意给出两条链表长度不相等的情况的)
解法如下图: