题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
比较粗心看漏了几次题目，导致多次出错。
几次出错
- 第一次没看到编译器里需要用它提供的链表进行编码，直接用了Java自带的List<>，在IDEA中写完准备复制到编译器才发现需要用他们提供的ListNode。
import java.util.*;
public class add_two_number {
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>() ;
l1.add(2) ;
l1.add(4) ;
l1.add(1) ;
l1.add(9) ;
List<Integer> l2 = new ArrayList<>() ;
l2.add(2);
l2.add(0);
l2.add(2);
l2.add(1);
System.out.println(addTwoList(l1 , l2));
}
private static List<Integer> numberToList(Integer num){
String s = num.toString() ;
char [] chars = s.toCharArray();
List<Integer> list = new ArrayList<>() ;
for (int i = 0 ; i < chars.length ; i ++){
list.add(Integer.parseInt(String.valueOf(chars[i]))) ;
}
return list ;
}
private static Integer listToNumber(List<Integer> list){
double num = 0 ;
for (int i = list.size() - 1 ; i >= 0 ; i --){
num += list.get(i) * Math.pow(10 , list.size() - 1 - i) ;
}
return Integer.valueOf((int) num);
}
private static List<Integer> addTwoList(List<Integer> l1 , List<Integer> l2){
Integer num = listToNumber(l1) + listToNumber(l2) ;
return numberToList(num) ;
}
}
- 第二次，使用了它提供的链表进行编码，在IDEA测试无误后，复制过去编译，几次编译都发现输出结果与预期结果不同，仔细一看题目才知要逆序，然后有了第三次。
public class add_two_numbers {
public static void main(String[] args) {
ListNode listNode = new ListNode(1) ;
listNode.add(5);
listNode.add(7);
ListNode listNode1 = new ListNode(2) ;
listNode1.add(3);
listNode1.add(7);
numberToList(listToNumber(listNode) + listToNumber(listNode1)).showList();
}
private static int listToNumber(ListNode l){
int num = 0 ;
ListNode temp = l ;
int length = 0 ;
while (temp.next != null){
length += 1 ;
temp = temp.next ;
}
temp = l ;
length = length ;
while (length >= 0){
num += temp.val * Math.pow(10 , length) ;
temp = temp.next ;
length -- ;
}
return num ;
}
private static ListNode numberToList(int num){
ListNode listNode = new ListNode() ;
ListNode temp = listNode ;
String s = String.valueOf(num) ;
char [] chars = s.toCharArray();
for (int i = 0 ; i < chars.length ; i ++){
temp.val = Character.getNumericValue(chars[i]);
if (i == chars.length - 1){
break;
}
temp.next = new ListNode();
temp = temp.next ;
}
return listNode ;
}
private static class ListNode { //简单功能的ListNode
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
private void add(int num) {
ListNode temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new ListNode(num);
}
private void showList() {
ListNode temp = this;
while (true) {
System.out.print(temp.val + "\t");
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
}
}
第三次终于在LeetCode提供的编译器里通过了，点击提交，解答错误，我的方法是将链表的值遍历成int类型，再相加转换成链表，它的测试用例是：
最后执行的输入：
[9]
[1,9,9,9,9,9,9,9,9,9]
结果已超出int类型的数据范围。
public class add_two_numbers2 {
public static void main(String[] args) {
ListNode2 l1 = new ListNode2(7) ;
l1.add(3);
l1.add(2);
ListNode2 l2 = new ListNode2(7) ;
l2.add(5);
l2.add(1);
numberToList(listToNumber(l1) + listToNumber(l2)).showList();
}
private static int listToNumber(ListNode2 l) {
int num = 0 ;
ListNode2 temp = l ;
int powNum = 0 ;
while (temp != null){
num += temp.val * Math.pow(10 , powNum) ;
temp = temp.next ;
powNum ++ ;
}
return num ;
}
private static ListNode2 numberToList(int num){
ListNode2 listNode2 = new ListNode2() ;
ListNode2 temp = listNode2 ;
StringBuffer sb = new StringBuffer(String.valueOf(num)) ;
sb = sb.reverse() ;
int index = 0 ;
while (index < sb.length()){
temp.val = Character.getNumericValue(sb.charAt(index)) ;
if (index == sb.length() - 1){
break;
}
temp.next = new ListNode2() ;
temp = temp.next ;
index ++ ;
}
return listNode2 ;
}
private static class ListNode2 {
int val;
ListNode2 next;
ListNode2() {
}
ListNode2(int val) {
this.val = val;
}
ListNode2(int val, ListNode2 next) {
this.val = val;
this.next = next;
}
private void add(int num) {
ListNode2 temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new ListNode2(num);
}
private void showList() {
ListNode2 temp = this;
while (true) {
System.out.print(temp.val + "\t");
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
}
}
第四次，将int类型换成了long，并使用了上次提交时给出的用例测试，出了正确结果，在次点击提交：解答错误
此次的测试用例是：
最后执行的输入：
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]
public class add_two_numbers2 {
public static void main(String[] args) {
ListNode2 l1 = new ListNode2(9) ;
ListNode2 l2 = new ListNode2(1) ;
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
numberToList(listToNumber(l1) + listToNumber(l2)).showList();
}
private static ListNode numberToList(long num){
ListNode listNode = new ListNode() ;
ListNode temp = listNode ;
StringBuffer sb = new StringBuffer(String.valueOf(num)) ;
sb = sb.reverse() ;
int index = 0 ;
while (index < sb.length()){
temp.val = Character.getNumericValue(sb.charAt(index)) ;
if (index == sb.length() - 1){
break;
}
temp.next = new ListNode() ;
temp = temp.next ;
index ++ ;
}
return listNode ;
}
private static long listToNumber(ListNode l) {
long num = 0 ;
ListNode temp = l ;
long powNum = 0 ;
while (temp != null){
num += temp.val * Math.pow(10 , powNum) ;
temp = temp.next ;
powNum ++ ;
}
return num ;
}
private static class ListNode2 {
int val;
ListNode2 next;
ListNode2() {
}
ListNode2(int val) {
this.val = val;
}
ListNode2(int val, ListNode2 next) {
this.val = val;
this.next = next;
}
private void add(int num) {
ListNode2 temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new ListNode2(num);
}
private void showList() {
ListNode2 temp = this;
while (true) {
System.out.print(temp.val + "\t");
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
}
}
？？？
人傻了，看来转换类型再相加再转回去的方法行不通了，只能另求他法。
最后终于通过了
- 最后的方法是，将两个链表对应节点的值相加，存到另一张链表上，类似于小时候学多位数加减法那样，只是这里相加是从头开始加，相加值大于等于10的，取余，向后进一位，后面也如此计算，直到两个链表皆为空，且无需再往后进位。
附上代码：
public class add_two_numbers3 {
public static void main(String[] args) {
ListNode2 l1 = new ListNode2(9) ;
ListNode2 l2 = new ListNode2(1) ;
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
l2.add(9);
addTwoList(l1 , l2).showList();
}
private static ListNode2 addTwoList(ListNode2 l1 , ListNode2 l2){
ListNode2 newList = new ListNode2() ;
ListNode2 temp1 = l1 ;
ListNode2 temp2 = l2 ;
ListNode2 newListTemp = newList ;
ListNode2 ZeroNode = new ListNode2(0) ;
int last = 0 ;
while (true){
if (temp1 == null){ //若该链表已空，将其指向前面已经定义好的，值为0的节点，避免后面相加出行空指针异常
temp1 = ZeroNode ;
}
if (temp2 == null){
temp2 = ZeroNode ;
}
newListTemp.val = (temp1.val + temp2.val + last) % 10 ;
last = (temp1.val + temp2.val + last) / 10;
temp1 = temp1.next ;
temp2 = temp2.next ;
if ((temp1 == null && temp2 == null) && last == 0){
break;
}
newListTemp.next = new ListNode2() ;
newListTemp = newListTemp.next ;
}
return newList ;
}
private static class ListNode2 {
int val;
ListNode2 next;
ListNode2() {
}
ListNode2(int val) {
this.val = val;
}
ListNode2(int val, ListNode2 next) {
this.val = val;
this.next = next;
}
private void add(int num) {
ListNode2 temp = this;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new ListNode2(num);
}
private void showList() {
ListNode2 temp = this;
while (true) {
System.out.print(temp.val + "\t");
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
}
}
做这道题花了好长时间，主要就是前面几次实在太粗心了，连续几次都没看清题目要求，也是把我自己给气笑了。最后做的正确结果也是有了思路之后，在IDEA里debug了好久才修改到正确的。
感兴趣的话也可以点击题目描述里的LeetCode链接，试试手或者看看别人的解法。