LeetCode每日一练（两数之和）
LeetCode每日一练（两数之和）
题目如下：
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
题目很好理解，就是给你两个链表，比如243和564，需要逆序得到链表所代表的的数值，分别是342和465，将这两个数相加，得到结果807，再逆序存回一个链表并返回。
了解题目的意思之后，我们先来分析一下，这道题思路还是比较简单的，首先遍历两个链表，并对遍历结果进行逆序处理，得到两个数，然后相加得到结果，再逆序存入链表。
首先我们需要得到两个链表所代表的数值：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 遍历l1链表得到数值
StringBuilder sb = new StringBuilder();
while (l1 != null) {
sb.append(l1.val);
l1 = l1.next;
}
// 将数值逆序
String str1 = sb.reverse().toString();
Integer num1 = Integer.valueOf(str1);
// 清空sb
sb.setLength(0);
// 以同样的方式得到链表l2的数值
while (l2 != null) {
sb.append(l2.val);
l2 = l2.next;
}
String str2 = sb.reverse().toString();
Integer num2 = Integer.valueOf(str2);
// 两数相加
int result = num1 + num2;
System.out.println(num1 + "+" + num2 + "=" + result);
return null;
}运行结果：
342+465=807得到结果之后，就创建一个新的链表，将结果逆序放入新链表中：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 遍历l1链表得到数值
StringBuilder sb = new StringBuilder();
while (l1 != null) {
sb.append(l1.val);
l1 = l1.next;
}
// 将数值逆序
String str1 = sb.reverse().toString();
Integer num1 = Integer.valueOf(str1);
// 清空sb
sb.setLength(0);
// 以同样的方式得到链表l2的数值
while (l2 != null) {
sb.append(l2.val);
l2 = l2.next;
}
String str2 = sb.reverse().toString();
Integer num2 = Integer.valueOf(str2);
// 两数相加
int result = num1 + num2;
// 将结果整理成链表
String strResult = String.valueOf(result);
char[] chars = strResult.toCharArray();
ListNode listNode = new ListNode();
ListNode temp = listNode;
for (int i = chars.length - 1; i >= 0; --i) {
if (i == 0) {
temp.val = Integer.parseInt(String.valueOf(chars[i]));
// 对于尾结点，其指针域为空
temp.next = null;
} else {
temp.val = Integer.parseInt(String.valueOf(chars[i]));
temp.next = new ListNode();
temp = temp.next;
}
}
return listNode;
}都是一些非常简单的链表操作，如果还不会链表的话，数据结构需要补补课了呦，遍历返回的链表就得到结果：
708怀着喜悦的心情将代码放到LeetCode上运行，结果没通过：
原来是测试数据太大了，导致int类型装不下，那就将其改为long类型：
......
Long num1 = Long.valueOf(str1);
Long num2 = Long.valueOf(str2);
Long result = num1 + num2;
......结果还是没有通过：
我的天，测试数据居然这么长，那没办法，我们将其改为BigDecimal就可以了，最终代码：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 遍历l1链表得到数值
StringBuilder sb = new StringBuilder();
while (l1 != null) {
sb.append(l1.val);
l1 = l1.next;
}
// 将数值逆序
String str1 = sb.reverse().toString();
BigDecimal decimal1 = new BigDecimal(str1);
// 清空sb
sb.setLength(0);
// 以同样的方式得到链表l2的数值
while (l2 != null) {
sb.append(l2.val);
l2 = l2.next;
}
String str2 = sb.reverse().toString();
BigDecimal decimal2 = new BigDecimal(str2);
// 两数相加
BigDecimal resultDecimal = decimal1.add(decimal2);
// 将结果整理成链表
String strResult = resultDecimal.toString();
char[] chars = strResult.toCharArray();
ListNode listNode = new ListNode();
ListNode temp = listNode;
for (int i = chars.length - 1; i >= 0; --i) {
if (i == 0) {
temp.val = Integer.parseInt(String.valueOf(chars[i]));
temp.next = null;
} else {
temp.val = Integer.parseInt(String.valueOf(chars[i]));
temp.next = new ListNode();
temp = temp.next;
}
}
return listNode;
}测试通过：
可以看到执行用时是比较长的，只击败了18.79%的用户，我们来分析一下导致执行用时过长的原因，首先是对链表的遍历，我们一共遍历了两次链表，然后是链表的创建，这些都是非常耗时的操作，有没有办法能够只进行一次遍历就完成题目的要求呢？
题目表示链表的数字是按逆序方式存储的，这刚好给了我们一个便利的处理方式，我们可以同时遍历两个链表，并分别取出两个链表同一位置上的两个数值，相加后直接放到新创建的链表中，比如243和564链表：
由于数值是逆序存储，所以链表的第一个元素其实是数值的最后一个数，将2和5相加得到7，故结果的最后一位数为7，再将其存入新的链表，作为第一个结点即可：
然后l1和l2后移一位：
该位置上的两个数相加结果为10，这里就需要考虑到进位的问题，要让当前位置的数值为0，并向前一位进1，只需让相加的结果除以10，就能够得到进位；比如10除以10等于1，就向前进1，23除以10等于2，就向前进2。再让相加的结果模10就能够得到当前位置的结果数，比如10模10等于0，当前位置就是0，23模10等于3，当前位置就是3。由此可知，结果的倒数第二个数为0，将其存入新的链表：
l1、l2继续后移：
该位置上的两个数相加等于7，需要注意还得加上进位，所以结果的第一位为8，存入新链表：
此时l1、l2后移，结果为空，故计算结束，这样我们就通过一次遍历直接得到了结果链表。
当然，我们还需要考虑两个链表不一样长的情况，比如：
对于这种情况，前面两个数的求法都是一样的，5加2等于7，存入新链表，6加4等于10，向前进1，将0存入新链表，此时l1、l2再后移，l1为空，但l2仍然有值，这时候我们给l1一个占位，让其等于0，这样就能够继续相加，此时4加0，再加上进位等于5，所以最终结果为：
由此得到代码：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 新链表的头指针、尾指针均初始化为null
ListNode head = null, tail = null;
// 初始化进位为0
int carry = 0;
// 同时遍历l1和l2链表
while (l1 != null || l2 != null) {
// 处理两个链表不等长的情况，若某个链表遍历结束，结点为null，则让其值等于0
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
// 两数相加，记得加上进位
int sum = n1 + n2 + carry;
// 采用尾插法建立新链表
if (head == null) {
head = tail = new ListNode(sum % 10); // 模10得到当前位置的数值
} else {
tail.next = new ListNode(sum % 10); // 模10得到当前位置的数值
tail = tail.next;
}
// 计算进位
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
// 若是两个链表遍历结束后，仍然有进位，则进位应成为新的一位
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}因为计算得到的结果需要按顺序依次放入新链表，故而这里采用尾插法建立新的链表。
最后将代码提交到LeetCode上，测试通过：
