問題：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類模擬鏈表功能碧查，實現(xiàn)大數(shù)字的加法皂林。
方法一（時間超限）：新建一個鏈表言津，每次新建一個結(jié)點货矮，將相加的結(jié)果存放到結(jié)點中，但是由于每次新建結(jié)點都需要new一個對象俺附，而new一個對象話費較長時間应民，所以考慮方法二但校；
方法二：由于每相加一位，輸入的兩鏈表在該位置的信息就沒用枷踏，所以將相加的結(jié)果同時存在兩鏈表該位置（這個過程所用時間應(yīng)該遠小于new一個對象）菩暗，最后如果兩鏈表長度不同，繼續(xù)在較長鏈表存放結(jié)果旭蠕，最后只需要新建一個結(jié)點停团。該方法可以通過旷坦。
源碼：
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("結(jié)果是-->");
while(l3!=null){
System.out.print(l3.val);
l3 = l3.next;
}
System.out.println();
long end = System.currentTimeMillis();
System.out.println("結(jié)束時間"+end);
System.out.println("總共運行時間->"+(end-start));
}
}
