/*
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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
*/
此題不能用暴力法算凿，即將 List1 和 List2 都轉(zhuǎn)化為數(shù)降宅，然后相加恍箭，然而筆者實(shí)現(xiàn)了這一暴力算法過程：
- 利用 10 的乘方來恢復(fù) List 所表示的數(shù)已卸，再將兩個(gè)數(shù)相加佛玄，將和作為字符串處理，將字符串中每一個(gè)字符所代表的數(shù)字插入到一個(gè)空鏈表頭引領(lǐng)的 List 中累澡，最后返回空鏈表頭的下一個(gè)節(jié)點(diǎn)
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Num = 0;
int num1 = 0;
int l2Num = 0;
int num2 = 0;
while(l1 != null) {
l1Num = l1Num + l1.val * (int)Math.pow(10, num1);
l1 = l1.next;
num1++;
}
while(l2 != null) {
l2Num = l2Num + l2.val * (int)Math.pow(10, num2);
l2 = l2.next;
num2++;
}
int sum = l1Num + l2Num;
// System.out.println(l1Num + " " + l2Num);
String sumString = sum + "";
System.out.println(sumString);
ListNode emptyHead = new ListNode(0);
ListNode curr = emptyHead;
for(int i = sumString.length() - 1; i >= 0; i--) {
ListNode Num = new ListNode(Integer.valueOf(sumString.charAt(i) + ""));
curr.next = Num;
curr = curr.next;
}
return emptyHead.next;
}
這樣雖然能夠滿足題目中給出的例子：（結(jié)果是 807 對應(yīng)的 7 -> 0 -> 8）
public static void main(String[] args) {
ListNode l11 = new ListNode(2);
ListNode l12 = new ListNode(4);
ListNode l13 = new ListNode(3);
l11.next = l12;
l12.next = l13;
ListNode l21 = new ListNode(5);
ListNode l22 = new ListNode(6);
ListNode l23 = new ListNode(4);
l21.next = l22;
l22.next = l23;
ListNode head = addTwoNumbers(l11,l21);
while(head != null) {
System.out.print(head.val);
head = head.next;
}
}
但是它存在一個(gè)致命的 Overflow 問題梦抢，即處理 long 類型整數(shù)時(shí)，會(huì)出現(xiàn)溢出：
public static void main(String[] args) {
ListNode l11 = new ListNode(9);
ListNode l21 = new ListNode(1);
ListNode l22 = new ListNode(9);
ListNode l23 = new ListNode(9);
ListNode l24 = new ListNode(9);
ListNode l25 = new ListNode(9);
ListNode l26 = new ListNode(9);
ListNode l27 = new ListNode(9);
ListNode l28 = new ListNode(9);
ListNode l29 = new ListNode(9);
ListNode l210 = new ListNode(9);
l21.next = l22;
l22.next = l23;
l23.next = l24;
l24.next = l25;
l25.next = l26;
l26.next = l27;
l27.next = l28;
l28.next = l29;
l29.next = l210;
ListNode head = addTwoNumbers(l11,l21);
while(head != null) {
System.out.print(head.val);
head = head.next;
}
}
- 其結(jié)果并不是 10000000000愧哟，而是 8045600141
故在提交時(shí)也不能通過
棄之奥吩，改用他法
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
// 與上法相同，創(chuàng)建空鏈表頭蕊梧，用來生成新鏈表返回空鏈表頭下一個(gè)節(jié)點(diǎn)
ListNode emptyHead = new ListNode(0);
ListNode curr = emptyHead;
ListNode p = l1;
ListNode q = l2;
// carry 是進(jìn)位符霞赫，如果兩個(gè)節(jié)點(diǎn)中的數(shù)字相加導(dǎo)致向下一位進(jìn)位，則將 carry 置成 1肥矢，不進(jìn)位 carry 為 0端衰，所以后續(xù) carry 參與節(jié)點(diǎn)中數(shù)字的相加
int carry = 0;
while(p != null || q != null) {
int x;
int y;
if(p == null) {
x = 0;
}
else {
x = p.val;
}
if(q == null) {
y = 0;
}
else {
y = q.val;
}
// 得到總和為表一節(jié)點(diǎn)數(shù)字加表二節(jié)點(diǎn)數(shù)字加進(jìn)位符
int sum = x + y + carry;
// 該節(jié)點(diǎn)的新數(shù)字為綜合除以 10 之后的余數(shù)
int newCurrNumber = (sum) % 10;
ListNode newNumber = new ListNode(newCurrNumber);
// 連接上之前的鏈表
curr.next = newNumber;
curr = curr.next;
// 如果和大于等于 10，進(jìn)位符為 1甘改，下一位（節(jié)點(diǎn)）的兩個(gè)數(shù)進(jìn)行計(jì)算時(shí)要加進(jìn)位符 1旅东，否則不進(jìn)位（進(jìn)位符為 0）
if(sum >= 10) {
carry = 1;
}
else {
carry = 0;
}
// l1 和 l2 向后遍歷
if(p != null) {
p = p.next;
}
if(q != null) {
q = q.next;
}
}
// 如果最后一次運(yùn)算過后，進(jìn)位符仍然為 1十艾，則說明產(chǎn)生了新的位玉锌，為表示新數(shù)字的鏈表創(chuàng)建一個(gè)新的節(jié)點(diǎn)
if(carry == 1) {
curr.next = new ListNode(carry);
}
// 返回空鏈表頭的下一個(gè)節(jié)點(diǎn)
return emptyHead.next;
}
這樣就通過了測試
