前言
就是要把leetcode刷完，每天一道题，每天进步一点点。
从零打卡leetcode之day 2
题目描述：
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，
它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 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)
(我是故意给出两条链表长度不相等的情况的)
解法如下图：
代码如下:
int cout = 0;//用来检查是否有进位,默认没有进位
ListNode head = null;//用来作为链表头
ListNode temp = head;//用来跟踪链表
//注意循环结束条件
while(l1 != null && l2 != null){
if(head == null){
head = new ListNode((l1.val + l2.val + cout) % 10);
temp = head;
}else{
temp.next = new ListNode((l1.val + l2.val + cout) % 10);
temp = temp.next;
}
//检查是否有进位
cout = (l1.val + l2.val + cout) / 10;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
temp.next = new ListNode((l1.val + cout) % 10);
cout = (l1.val + cout) / 10;
l1 = l1.next;
temp = temp.next;
}
while(l2 != null){
temp.next = new ListNode((l2.val + cout) % 10);
cout = (l2.val + cout) / 10;
l2 = l2.next;
temp = temp.next;
}
//最后还得在检测一下时候最高位有进位
if(cout == 1){
temp.next = new ListNode(cout);
}
return head;
这里需要注意的一些点：
-
就是第一个循环的结束条件.
-
当循环结束之后，还得把那条比较长的链表剩余的部分再循环一遍。
- 最后还得看一下是否最高位有进位。
我觉得这道题在解法思路上还是比较简单，不过并不意味着做起来简单，因为这道题如果不仔细看，还是很容易出错的，细节点不叫多。
不过
除了方法二，我是不知道还要其他什么比较好的方法了，但是我是觉得方法二里面的代码有点多，于是绞尽脑汁，各种简化，写出了一份代码比较简练的精简代码。放出来给各位看看：
//作为头节点，且最后返回时不要这个头节点
ListNode head = new ListNode(0);
ListNode temp = head;//跟踪
int cout = 0;
while(l1 != null || l2 != null || cout != 0){
if(l1 != null){
cout += l1.val;
l1 = l1.next;
}
if(l2 != null){
cout += l2.val;
l2 = l2.next;
}
temp.next = new ListNode(cout % 10);
temp = temp.next;
cout = cout / 10;
}
return head.next;
先得意一下：虽然大家都能想到方法二，不过我就不信你能比我的简洁。哈哈哈
几点说明:
- 先把头节点直接new出来，可以省略判断语句。
- 以前的while循环是判断两个链表都不为空，不过我现在换了一种想法，因为i你想我，只要有一个链表是不为空的，或者只要coun=1，那么我们就得继续处理，于是乎…..
此题到此结束
完
