问题：You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8
语言：java
思路：使用java类模拟链表功能，实现大数字的加法。
方法一（时间超限）：新建一个链表，每次新建一个结点，将相加的结果存放到结点中，但是由于每次新建结点都需要new一个对象，而new一个对象话费较长时间，所以考虑方法二；
方法二：由于每相加一位，输入的两链表在该位置的信息就没用，所以将相加的结果同时存在两链表该位置（这个过程所用时间应该远小于new一个对象），最后如果两链表长度不同，继续在较长链表存放结果，最后只需要新建一个结点。该方法可以通过。
源码：
public class Add_Two_Numbers {
public static ListNode addTwoNumbers(ListNode l1,ListNode l2){
int sum = 0;
ListNode head1 = l1;
ListNode head2 = l2;
while(l1 != null && l2 != null)
{
int temp = l1.val+l2.val+sum;
l1.val = temp%10;
l2.val = temp%10;
sum = temp/10;
l1 = l1.next;
l2 = l2.next;
System.out.println(0);
}
if(l1 != null){
while(l1 != null){
System.out.println(1);
int temp = l1.val + sum;
l1.val = temp%10;
sum = temp/10;
l1 = l1.next;
}
if(sum != 0){
ListNode nodeNext = head1;
while(nodeNext.next!=null){
nodeNext = nodeNext.next;
}
nodeNext.next = new ListNode(sum);
}
return head1;
}
else if(l2 != null){
while(l2 != null){
System.out.println(2);
int temp = l2.val + sum;
l2.val = temp%10;
sum = temp/10;
l2 = l2.next;
}
if(sum != 0){
ListNode nodeNext = head2;
while(nodeNext.next!=null){
nodeNext = nodeNext.next;
}
nodeNext.next = new ListNode(sum);
}
return head2;
}
else{
System.out.println(3);
if(sum != 0){
System.out.println("sum->"+sum);
ListNode nodeNext = head1;
while(nodeNext.next!=null){
nodeNext = nodeNext.next;
}
nodeNext.next = new ListNode(sum);
}
System.out.println(5);
return head1;
}
}
public static void main(String[] args){
long start = System.currentTimeMillis();
System.out.println("开始时间"+start);
ListNode l1 = new ListNode(9);
ListNode head = l1;
head.next = new ListNode(9);
// head = head.next;
// head.next = new ListNode(6);
// head = head.next;
// head.next = new ListNode(0);
// head = head.next;
// head.next = new ListNode(5);
// head = head.next;
// head.next = new ListNode(8);
// head = head.next;
// head.next = new ListNode(1);
// head = head.next;
// head.next = new ListNode(0);
// head = head.next;
// head.next = new ListNode(7);
// head = head.next;
ListNode l2 = new ListNode(5);
// head = l2;
// head.next = new ListNode(2);
// head = head.next;
// head.next = new ListNode(5);
// head = head.next;
// head.next = new ListNode(7);
// head = head.next;
// head.next = new ListNode(9);
// head = head.next;
// head.next = new ListNode(1);
// head = head.next;
// head.next = new ListNode(0);
// head = head.next;
// head.next = new ListNode(2);
// head = head.next;
// head.next = new ListNode(2);
// head = head.next;
// head.next = new ListNode(1);
// head = head.next;
ListNode l3 = addTwoNumbers(l1,l2);
System.out.print("结果是-->");
while(l3!=null){
System.out.print(l3.val);
l3 = l3.next;
}
System.out.println();
long end = System.currentTimeMillis();
System.out.println("结束时间"+end);
System.out.println("总共运行时间->"+(end-start));
}
}
